Exodus 35:3 "You shall kindle no fire in all your dwelling places on the Sabbath day."
The key word here seems to be "kindle".
Does this mean they were only restricted from starting a fire on the Sabbath, or that they could not have one at all? If not at all, what would their source of heat be in the winter on Sabbath days?
While the Karaites interpreted this verse to mean that no flames may be burning on the Sabbath at all, the traditional Rabbinic interpretation (see Mechilta 35:3) is that fire may burn on the Sabbath so long as it was lit beforehand. No fuel may be ignited on the Sabbath (including, for example, pouring more oil into a burning lamp). (See at length Ibn Ezra's Short Commentary ad loc., where he records a debate he had with a Karaite on the matter.)
Thus, Jews following that interpretation have traditions that enhance comfort on the Sabbath like lighting candles before the Sabbath to be able to see at night, and leaving ovens on from before Sabbath to be able to eat hot food. In the early middle ages this dispute became quite a shibboleth, with Jews who didn't eat hot food on the Sabbath being accused of heresy. Some more about the Rabbinical responses to that can be found in Hebrew here.
The Spoken Law recorded in the Talmud gives many more details of prohibited labor on the Sabbath than what you'd see in a strict literal reading of the verse. Moses commands the people to keep the Sabbath, and then to build the Tabernacle. The Talmud concludes that any act of physical creation used to build the Tabernacle is prohibited "work" on the Sabbath. For instance you'll never find a verse that weaving is prohibited on Sabbath, but traditional Judaism follows the Talmud that as it was an act of labor building the Tabernacle, it's prohibited.
(The commentaries address why Exodus chose to single out kindling over any other labor; one suggestion is that kindling tends to be an enabler rather than the final product for many labors -- I am kindling so I can dye this wool or cast this gold -- and yet it is still prohibited.)
The Talmud's interpretation of the prohibition of kindling includes both starting and fueling a flame. Therefore adding fuel to an existing fire would be prohibited.
As for how people managed: ideally, leave enough wood around from before the Sabbath to last the whole day. Otherwise, often a non-Jew was asked (or employed) to add fuel. While generally we try to avoid asking a non-Jew to do labor on the Sabbath that we can't do, there is a dispensation for those who are unwell, and we don't want people to get frostbite.
