Redshifting of Light and the expansion of the universe
Dear QEntanglement, the photons - e.g. cosmic microwave background photons - are increasing their wavelength proportionally to the linear expansion of the Universe, $a(t)$, and their energy correspondingly drops as $1/a(t)$. Where does the energy go? It just disappears.
Energy is not conserved in cosmology.
Much more generally, the total energy conservation law becomes either invalid or vacuous in general relativity unless one guarantees that physics occurs in an asymptotically flat - or another asymptotically static - Universe. That's because the energy conservation law arises from the time-translational symmetry, via Noether's theorem, and this symmetry is broken in generic situations in general relativity. See
http://motls.blogspot.com/2010/08/why-and-how-energy-is-not-conserved-in.html
Why energy is not conserved in cosmology
Cosmic inflation is the most extreme example - the energy density stays constant (a version of the cosmological constant with a very high value) but the total volume of the Universe exponentially grows, so the total energy exponentially grows, too. That's why Alan Guth, the main father of inflation, said that "the Universe is the ultimate free lunch". This mechanism (inflation) able to produce exponentially huge masses in a reasonable time frame is the explanation why the mass of the visible Universe is so much greater than the Planck mass, a natural microscopic unit of mass.
Other answers have covered the key points correctly, but I'll jump in too, maybe emphasizing a slightly different angle.
It's not just that energy is not conserved -- even defining the total energy of the Universe (or even the total energy in any reasonably large volume) is problematic and, in some sense, unnatural.
What people usually have in mind when they talk about the total energy of the Universe (or a large volume -- from now on I'll stop writing that) is something like the following: Figure out the energy of each particle in that volume, and add 'em up. That's a sensible procedure for figuring out total energy in other contexts: it works great if you want to talk about the energy in all of the air molecules in this room. But it only works if all of the individual energies are determined in the same inertial reference frame. And in the expanding Universe (or any curved spacetime), there are no inertial reference frames that cover the whole region.
When people worry about energy non-conservation as applied to CMB photons, what they're implicitly doing is calculating each photon's energy in the local comoving reference frame (the one that's "at rest" with respect to the expansion). But all of the different comoving frames are in motion with respect to each other, so it's "illegal" to add up those energies and call the result a total energy.
Think of a Newtonian analogy: if one person measures the kinetic energy of something on board a moving airplane, and another person measures the kinetic energy of a different object on the ground, you can't add them up to get a total energy. And certainly the sum of those two things won't be a conserved quantity.
Just to be clear: I know that there are a bunch of contexts (e.g., asymptotically flat spacetimes) in which it does make sense to talk about energy conservation in various forms. But in this specific context, I think that the above is the essence of the issue.