Gas furnace air is cooler (but NOT COLD) during bitter cold days - why?
There should be a nameplate on the unit, which among other things will list the expected temperature rise across the heat exchanger.  This value tells you how much the furnace should be expected to raise the temperature of the incoming air.  

Furnaces do not put out an exact temperature air, the outlet air temperature is always based on the inlet air temperature. For example. If you have a furnace with a 60°F temperature rise rating, and an inlet air temperature of 65°F. You should expect 125°F air coming out of the furnace. If you have an inlet air temperature of 45°F, going into the same furnace.  You should only expect 105°F air to come out.

Add to that the fact that some ducts might be run in exterior walls or unconditioned space, and you could be losing heat before the air actually reaches you. 

It sounds like either the furnace is undersized, dirty, old, or the home is not insulated well.  Make sure the filter is clean, all registers and returns are open and unobstructed, and have the heat exchanger cleaned and inspected by an HVAC technician.