Does humidity make cold air feel colder? I sometimes hear stories where people compare their feelings in winter in different places in the world.
It goes like

in city X the temperature was the same as in city Y, but the humidity made me feel much colder...

or 

oh well, -20°C would be cold, but the humidity was low, so it felt OK

so it implies that humidity somehow makes it feel colder. I am talking about temperatures below freezing (-30...0°C).
Does this have any physical explanation, or is it some sort of psychological phenomenon?
 A: Higher humidity means that there is a greater concentration of water in the air.  Water has a higher specific heat than nitrogen gas, thus hot water can give off more heat (and cold water can absorb more heat).
An everyday example of this is how diving into a pool that's just above 0 degrees Celcius feels much much colder than being outside in air that's 0 degrees. Similarly, cold air with high humidity will reduce the temperature of our bodies faster than air with low humidity.
A: High humidity means a lot of water vapor in air, and water has a higher thermal capacity (heat needed to raise the substance 1'C) compared to air. This means that humid air will absorb more heat from your body and therefore will make you feel cooler.
A: Various types of apparent temperature have been developed to combine air temperature and air humidity. For higher temperatures, there are quantitative scales, such as the heat index. For lower temperatures, a related interplay was identified only qualitatively; e.g., in a 2012 textbook:

High humidity and low temperatures cause the air to feel chilly

Or in The Columbia Electronic Encyclopedia

Cold air with high relative humidity "feels" colder than dry air of
  the same temperature because high humidity in cold weather increases
  the conduction of heat from the body. 

Or in Popular Mechanics:

There has been controversy over why damp cold air feels colder than
  dry cold air. Some believe it is because when the humidity is high our
  skin and clothing become moist and are better conductors of heat, so
  there is more cooling by conduction.

A useful concept is thermal comfort, which considers many other factors, such as skin wetness and cloth friction. (I've started a section at Wikipedia).
A: Also, at lower temperatures the air cannot hold as much water vapor so lower temperatures may not feel as cold as higher temperatures.
A: Insulation, insulation, insulation!
Your body is constant +36C. Your clothes are insulators. If air humidity gets higher, clothes insulation gets lower and you feel colder. Just wear humid tight outer one.  
