Stone houses are very expensive at the start, however if you feel you can manage this proceed. Even on these settings most of your settlement should not be freezing provided they have homes and firewood/coal. This may be due to the citizens straying far from home, the further they travel to do something, the longer it takes them to get warm again (thus leading to freezing). During early winters it is best to have your citizens near to your towns center.
A popular early game start (only on hard start) for maximising resources for population is to build a boarding house, this will allow multiple families to reside in one building and share its heat, therefore reducing firewood consumption.
Stone houses and warm coats are useful in that they heat your citizens greater, therefore they stay warm longer and dont struggle in the cold as much. However this becomes an issue mostly in the later game when your map is starting to lack surface resources and citizens must travel a great distance to retrieve them, or travel to their workplace (if no nearby housing).
As tjd points out: warm coats help your town operate more efficiently in that compared to normal coats, citizens can spend longer outside in the cold before returning home to warm up. This means that people work longer before returning home, potentially over a great distance. Travelling from home to work is one of the biggest time sinks for citizens.
If you started on easy and got lucky by starting with sheep, then feel free to build a pasture for them and set your tailor to make warm clothes (but be aware, your citizens will not use them until their current coat deteriorates).
In conclusion, best starting strategy for heat is to concentrate your village and its efforts in one location and remembering that a resource building with only half its radius available is still pretty effective (a fair trade-off for the proximity to start with). Always keep a good store of firewood (or coal if your desperate) and clothes (any are fine, but upgrading is easy once you have sheep and/or a trading port).
Stone houses should be built when you can afford them and it wont break the bank, typically I wait until the inhabitants are dieing of old age then upgrade.