Remote start is only part of the story. Until your engine warms up, DOD and DFCO (Decel Fuel Cut Off) aren't enabled and it takes longer to warm up in the winter (obviously). Also, your torque converter won't lock until the transmission warms up, and in the winter it's usually the engine coolant that warms the transmission fluid up so there is a decent lag there too (you can watch your trans temp increase faster after the thermostat opens). Combine all three not kicking on until you've driven for a bit, throw in higher viscousity fluids, and you lose a lot of mileage unless you are travelling long distances. Also, I slip the tires a lot more in the winter and so I can't accelerate as hard. You want a decent load on the engine when accelerating to get good efficiency, so you lose mileage there too. Firm acceleration (not WOT, lol) without overshooting your target speed followed by a steady light foot gives the best mileage for most cars. Finally, pusing through slush and snow requires more torque than rolling along dry pavement, hurting mileage more when the roads aren't plowed.
The other part of the equation is winter gas. Winter gas is reformulated with additives (a google search of winter gas in your state should kick them up if you are interested) that help the gas vaporize and increase octane rating. But, with higher octane and lower density fuel you have less energy per gallon and so you get worse mileage.
FWIW, I got 19+ in the winter and 22+ in the summer before I started modding, but I also run winter tires which have a higher rolling resistance too. I was at 22+ after my MAF tune until the snow hit, now it's slowly creeping down.
Final Tip: make sure you put some more air in your tires because colder air is more dense and your tire pressure drops when it is cold (pV = nRT).