Intuitively cold winter air is cold, but that's just our perspective. From a physics perspective any air that exists anywhere on this planet at any time has still got huge amounts of heat stored in it (it's literally hundreds of degrees above absolute zero, the most blisteringly cold arctic air still represents a huge reservoir of physical heat energy even when it's cold enough to kill us). A heat pump doesn't care about how heat feels to humans, it uses physics: specifically evaporation and condensation of refrigerants to extract heat from the cold winter air outside (making that air even colder while the refrigerant absorbs heat from it) and move it indoors (making it warmer when the refrigerant releases the heat).

To use a water level analogy, the heat pump moves its heat out of an absolutely massive heat reservoir (the planet's atmosphere) that at any point might be slightly lower or higher than the level you actually want, and deposits the results of its pumping into a tiny reservoir (your indoor air) that it is responsible for controlling the heat level of. In both cases there is lots and lots of water (in the analogy, heat) available to pump around and the contents of your little tank makes no real significant difference either way, depending on how much water you need in that tank you can easily pump it in either direction you want, within reason, but eventually if the water levels start to get too different, you start running into practical problems with pressure and the amount of power you need to pump the water level up that high to overcome the height difference, and can also run into problems with inlets being uncovered if the water level drops too low. In the analogy this represents the range of temperatures and pressures where the refrigerant can still change between a gas or a liquid, which is determined by the design of the system and the refrigerant used.

Air conditioners do the same thing (in fact essentially ARE the same thing) as heat pumps, it just makes more sense to us intuitively because we're familiar with how they work, and are unfamiliar with the idea of this principle being reversed. Imagine if you put the hot-air blasting outdoor part of an air conditioner inside, and put the cold part that normally lives inside your house, outside. Now turn it on, and it starts working as a heater, and it's making the outdoors colder for no reason, and we call this "wasteful" but when you actually need heat it's actually not wasteful. So we add a reversing valve so you can make either end the hot side or the cold side, as needed, and you've got a heat pump. They sometimes select different refrigerants that are more efficient across the desired temperature ranges and they will have some different sizing considerations and mechanical needs to operate optimally, but fundamentally they're the same kind of machine, just with a slight rearrangement of the plumbing.