How exactly do heat pumps work in a cold climate?
A heat pump transfers energy. I expect you've noted that the outside part of your A/C unit is really really hot in the summer. That's the energy from inside your house being transferred to the outside.

In the winter, the direction is reversed. The energy in cold air is substantially less than that of warm air, but there is energy there. The heat pump removes the energy from the cold air, making the outside discharge even colder (just like inside, during the summer) and transfers that energy inside to warm things up.

Heat pumps are usually equipped with a resistance heater for those days when the cold air is too cold to have any energy transferred effectively. The colder parts of the world will have less effective heat pumps. 

High Performance HVAC suggests that in colder areas, the energy source for a heat pump during the winter would not be the outside air, but rather a warmer source for heat exchange. A geothermal source (ground water loop) will contain far more energy during the winter as well as provide a good heat sink for summer operation.

Such systems will be more expensive to install, but will be less expensive (more effective) during the winter months, keeping the abode warm.

The above link also references electricity costs as a factor to determine suitability for heat pump selection, as well as other considerations.

I live in the Southeast and the heat pump aux heater never engages during the winter. It is a very efficient air conditioner in the summer, saving electricity cost over the equivalent non-heat pump design. Of course, the heat pump is a newer technology than the A/C unit it replaced, which may have provided for lower cost operation as well.