Question: We often seem to accept the idea that there were periods of time in which the entire surface of Earth was frozen, for the most part. This implies that there were periods of time in which the entire surface was NOT frozen over. Thus, there must have been heat and energy present on the surface. How did all that energy move to cause an ice age? It seems absurd for all that energy to just radiate into space or move deep into the Earth.

Answer: 
Of course it isn't "absurd", and looking at the ball-park energy budget figures you'll see why:

First, I don't think anyone is claiming the Earth is completely frozen. More of a "slushy at the Equator" scenario. But let's assume an average 1 km thickness of ice for arguments sake (i.e. probably an exaggeration although polar ice would be thicker).

The current thermal budget [can be found here](http://en.wikipedia.org/wiki/Earth%27s_energy_budget%20including%20references.).

Pertinent figures:

Geothermal heat flow (vertically through the rock, primarily from radioactive decay & cooling) is ~$0.084\ \mathrm{W/m^2}$.

Solar input: $340 \mathrm{W/m^2}$ About a quarter of this is reflected back but this will vary according to conditions (e.g. ice cover, clouds, etc). Assume no reflection. (yes the presence of ice would cause reflection - but it may also reduce cloud cover due to reduced evaporation?).

Note: geothermal energy is tiny relative to solar flux, so we'll ignore it.

That 1 km of ice = 1000m3 of ice (per square meter).

Let's assume that the melting process would also involve an increase in 10C in additional to the latent heat of melting (ie. yes we melt the water but we also increase its temperature a bit).

Total energy required (per $\mathrm{m^3}$) = (Temp increase \times Thermal capacity of water + Latent heat of melting) × volume.

So if we plug in our numbers, that would be:

$$(10 \times 4.2 + 334) \times 10^6 \times 1000$$
$$= 3.8 \times 10^{11}\ \mathrm{Joules}$$

Heat flux for the same area is $340\ \mathrm{J/s}$
So time for the required energy to melt the ice = $3.8 \times 10^{11} / 340 = 35\ \mathrm{years}$.

You could argue about my ball-park estimates. For example there would be more albedo reflection to melt the ice (=takes longer). And you may not necessarily have to increase the temperature of the water as much ( =>takes less time), and much of the Earth would not have 1 km of ice (=>takes less time). But this gives you a ball park "yes it is feasible".

---

Edit: I read the question a bit quickly - the above shows it is 'easy' to get from an ice planet to an ice-free planet. But the converse is also true. The amount of energy that keeps the Earth ice free can easily be added/subtracted over a timescale of a few centuries, just from solar and atmospheric effects.
One cause of glaciation on earth is dust from volcanic activities ie you have heard the term volcanic or nuclear winter.

During glaciation continental plates with a mile or two of ice piled upon them increase vastly in weight and actually sink. When we see a rock we see a hard stone object, but that rock within the earth under a vast amount of pressure is not "rock" solid, it is more the like peanut butter, it is soft and pliable. This is how continental plates are able to sink under the weight of a mile or two thick sheet of ice.

Not only do the continental plates have weight pushing down on this peanut butter like rock beneath us, the oceans also have weight and they as well push the plates beneath them down into this peanut butter like stone.

During glacial maximums ocean levels drop by as much as 400 feet, so what is currently 400 feet underwater was dry land during the last glacial maximum. This loss of 400 feet of water across all the oceans of the earth greatly reduces weight upon the ocean floors. That same water is turned to snow and collects as ice on the continental plates this adds that same weight now to the continental plates. So the oceanic plates raise while the continental plates drop.

During interglacial periods you get a lightening of continental plates and the oceanic plates become heavier with the return of high ocean water levels ie global sea level rise such as we are experiencing currently. Continental plates rise and oceanic plates drop. This reaction is not immediate, again if you imagine peanut butter if you put a board over several inches of peanut butter and add weight to the board it takes some time for the peanut butter to squish out the sides, the same with the continental plates and the soft stone they sit atop of. It takes thousands of years for the continental plates to rebound to their original height. During this rebounding of the continental plates and the dropping of the oceanic plates volcanic activity slowly starts to increase. Eventually it is only a matter of time before you get another great volcanic eruption due the plate movement that produces a great deal of ash in the atmosphere, this continues again and again with increased levels of volcanic activity. This ash reflects light back into space before it is able to reach and warm the surface, thereby reducing average global temperatures. 

This is certainly not the only mechanism that controls glacial maximum and interglacial periods but it does work in concert with the afore written answers to your question. The normal condition for our planet during human existence is glacial maximum conditions, what we are experiencing now an "interglacial" period exists only about 20% of the time somewhere on average of about 20k years per 100k years. This is the second interglacial period in the last 100k years. You have go back to 120k to 130k years for the next previous interglacial period.