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.
What's not been touched yet, and the current answers do cover a lot of ground, is the variability of solar input.  

Even IF the amount of energy radiated out by the earth remains the same (and it probably would, roughly), solar input is highly variable and is a major factor in determining the total energy budget of the planet.  

Even a small change can have far reaching consequences. Thus if the sun's output goes down by only a few percent (and that's well within its variability even over the 11 year sunspot cycle) temperatures on earth will swing with that (over that short a cycle that's pretty much averaged out by changes in ocean currents). If such a "dip" lasts longer, think a few centuries, you get a "little ice age" as we just emerged from in the 19th century (and by some accounts may be on the verge of slipping into the next, as the sun is again seemingly rather inactive).  

And the sun has longer cycles, such a low activity cycle lasting a few thousand years can well drop the earth into a full scale ice age. And as the ice sheets grow, reflection goes up, less energy heats the planet, less clouds form. Until the sun enters a high activity phase again, the planet will remain (relatively) cold.  

As said, this is unlikely to cause the entire planet to disappear under a blanket of ice. The last major ice age "only" came down to about the latitude of the Rhine delta in Europe for example.