No heaters, no artificial fiber clothing to layer, etc.
Wool is an amazing fiber that has been used since prehistoric times -- it is strong, long-lasting, and rivals modern polymers in its ability to insulate. It also continues to insulate when wet, unlike many (most?) plant fibers and some polymers. Synthetic polymers compete with wool in their weight; wool is a heavy fabric.
Our ancestors experimented with ways to increase the efficiency of an open fire. Two approaches were common: the use of heat sinks, generally in the form of large masonry "furnaces", and the recycling of heat from smoke, in the form of "bed stoves" (often called "rocket stoves" today), hypocausts, etc.
There were also more primitive methods, like the Iroquois long-house, where there were fire pits between each bank of beds. The round shape of the long-house and many other ancient peoples' housing was more heat-efficient than peaked roofs.
Here's some further reading:
MOD NOTE
This post is attracting an above-average number of below-average answers. Comments in /r/AskHistorians need to be comprehensive and informative.
There are actual historical accounts and archaeological evidence of how people in the past dealt with cold weather. There are even accounts of winters in Boston in the past. Please draw upon them and do not simply offer your opinion/speculation.
We can glean a lot of information from Otzi the iceman found in 1991 in the Otzal Alps on the border of Italy and Austria. He lived about 5,300 years ago and the great thing is he was discovered with most of his clothing and a pack full of gear intact.
He wore multiple layers of neolithic sheeps wool and other hides, and wide-based, waterproofed snow shoes. In his pack was a pretty advanced fire-starting kit containing a variety if sparking minerals and fungus tinders.
To me Otzi is a fabulous reminder that our ancient ancestors had no less ingenuity than modern man, and indeed were so much closer to the elements than our sheltered selves that they likely had a far greater knowledge of how to survive, feed, shelter and clothe themselves than any of us today ever will.
Edit: age mistake corrected.
I see many great answers but I think some people are forgetting the number one way our ancestors survived extreme cold.
Historically people tended to live in places that didn't have extreme cold or at least not often.
Check out this swell map of population by latitude in 2000 AD The worldwide average is somewhere around 27 degrees north. Now I know what you're thinking that's 2000 AD what about 2000 BC. Well the population numbers are harder to come up with but a listing of the places that are located at 27 degrees latitude gives a pretty good indication that it has been a nice place to live for quite awhile. Wikipedia 27th parallel north lots of nice places like Modern India, Iraq, Iran, Florida, Southern China, Algeria.
Of course climate has varied over time but the same general trends are in most cases applicable. Bostons average January high temperature is 37 degrees Fahrenheit. Orlando Florida's average high temperature is 71 degrees Fahrenheit. But Rome and Boston are at the same latitude. Yes, but Rome's average high is 54 degrees Fahrenheit because of the warmer waters of the Mediterranean. Visit The Weather Channel to have fun looking up cities of your own.
I know that there are thousands of examples of people living in cold places or of cold snaps passing through usually warmer places. However, that doesn't change the fact that the majority of people live in areas where extreme cold is not a common occurrence.
Anything that blocks the wind will cancel the effect of wind chill. If it is very cold then your insulated clothing will cover every part but the face. One Inuit (the masters of this sort of technology) approach is to make an extended hood with lots of fur on the edge to break up the wind. Some pics:
http://www.johntyman.com/arctic/inuit201.html
http://angelasancartier.net/inuit-and-arctic-dress-materials-technology
Edit: will -> wind, grammar
In my region, by digging holes. Beginning about 5,000 years ago, and continuing into the historic period, natives of the Northwest used semi-subterranean houses adjacent to large bodies of water to keep warm. The Columbia Plateau can get pretty cold. Native houses in that region were around a meter deep and had a wood superstructure and earth covering. Early on, ca. 5-6,000 BP, the houses were fairly small, about 5-7 m in diameter. Later they would get larger and elongated. Being at least partially under ground and the earth insulation raised the living area temperature significantly. Here is a cartoonish reconstruction. But you get the idea. House pits were used throughout North America during various periods of prehistory. They are pretty common.
The definitive work on Native Plateau Architecture is Native American Dwellings and Attendant Structures of the Southern Plateau Harvey S. Rice, 1985. Eastern Washington Reports in Archaeology and History, Cheney.
Edit: This is what the archaeological remains look like.
I do a lot of Renaissance reenactment, and along with wearing many layers of cotton and an outer layer of wool, we have small to large-ish rocks always sitting on hearths of fires in order to keep them warm, so they serve like little pocket hand warmers. When one rock gets cold, you switch it out for a hot one, and you'd be surprised how warm it keeps you when you have to walk around in cold and wind for long periods. Does anyone know if this actually happened in the past?
Since you mentioned Boston, I thought I'd mention how this was handled circa 1600. For clothing, I'll quote from from Howard Russel's Indian New England before the Mayflower:
In winter, to Europeans, the natives seemed strangely indifferent to the chill. In southern New England men wore over the left shoulder, and caught together there, a supple tanned skin from a moose, deer, or bear (perhaps more than one), hair side in, sewed or caught together under the right arm, and perhaps ornamented with colored designs: if a deerskin, its tail was wound about the waist. To shield the exposed right arm, they wore the pelt of a smaller animal, perhaps a deep-furred wildcat splotched with white, or a beaver or otter. This hung from the shoulder, leaving the arm free. Raccoon skins, the tails hanging loose, were especially popular. [...] Women wore knee-length skirts of skin and, in winter, a cloak formed from two deerskins, dropping from the shoulders and sometimes dragging behind. Leather leggings, supported also by the waist belt, protected the calves and and ankles against injury from sticks and briars; they were longer for men and boys than for women. For travel, moccasins of moose or deer skin completed the clothing.
For housing, I'll focus on the permanent wigwams in the villages. The temporary wigwams used at hunting and fishing camps are similar, but smaller and simpler. As Russel says, "the wigwam where the family passed the winter was no makeshift, but a tight, warm, comfortable dwelling." In Massachusetts, local wigwams didn't have the classic dome-shape that you're likely to see if you look up "wigwams" online. Here they more resemble truncated longhouses (like this). The wigwam's frame was covered with tightly woven mats (typically made from reeds) that are sewn together. The outside a layer of bark panels, also sewn together, was usually added. During winter, another layer of mats would be added as an additional layer of insulation to the inside.
In the center of home, a fire burned and the smoke escaped through a hole in the roof about a foot and a half wide. This whole wasn't completely exposed, and panel or hide that kept it partially covered could be manipulated with a string inside the home to adjust its position.
Low platforms lined the walls and were covered with deerskins, more reed mats, or sealskins if they were available. This was the basic furnishing for the home, serving as both seats during the day and beds at night. During winter, the blankets made from bear, otter, beaver, or raccoon fur were used while sleeping.
At least some English colonists (Daniel Gookin, for example) regarded these homes as being warmer than their own.
Additionally how much colder did it get in prehistoric times? Especially as close to the last ice age as humans were around?
What did they use for waterproofing? Animal skins or something? I couldn't imagine working outside all day in the snow with the shoes they would've had.
If I may ask a question in a similar category: I live in Australia, and in Summer it's regularly around 40°C. How did people that settle hot areas, especially European colonisers who live in generally colder climates, deal with such heat?
Follow-up question: how did people survive in areas of extreme heat? In the Gangetic Plain for instance, which was historically very densely populated, the mercury very often hits well into the 40s during summer, yet it is considered gospel that the settlement of places like Phoenix could not have been possible without the invention of air-con.
I would like to know about my ancestors, the aboriginals. How did they survive in the climates as far north as Northern Manitoba?
Korean Ondols (a kind of underfloor heating mechanism) have been found in archeological sites dating to 1000BCE. So there's that. This is in part why most Koreans prefer heated floors in their apartments, and often sleep on thin pads on said heated floor. (Something I've done for six weeks and rather enjoyed it.)
The infamous double negative
