1. Igloos
 2. Caves

Of course, you'll need a fire of some sort, but if you can vent the smoke and can keep the opening protected, you can make it comfortably warm in a number of different settings even with medieval tech because we've been keeping ourselves warm in cold settings for millennia.