Have red shifted photons lost energy and where did it go? I think the title says it. Did expansion of the universe steal the energy somehow?
 A: Energy isn't a nice concept in GR, so all I'm giving is an intuitive way of looking at it.
For gravitationally redshifted stuff:
A photon has energy, thus it gravitates (as energy can gravitate analogous to mass from $E=mc^2$), thus it has some (negative) gravitational potential energy when on the surface of a planet. If it's emitted, its GPE eventually becomes 0. So, this increase in GPE had to come from somewhere: the photon's redshift gave the energy. It's pretty much the same thing that happens when you throw a ball up. It loses kinetic energy (slows down).
The GPE in relativity is basically related to the energy stored in spacetime curvature; in a complicated way that I don't know.
For a normally redshifted photon from a moving body: Energy need not be conserved if you swith frames. Energy is different from each reference frame.
See the answers to the question provided by Qmechanic above as well. Over there, they're talking about the entire universe, though, which leads to additional issues.
A: The short answer is "yes". The energy lost from the photons is taken up by the energy in the gravitational field. Of course energy is a relative concept but if you take the simplest case of a spatially flat homogeneous cosmology with no cosmological constant then the equation for energy in an expanding volume $V(t) = a(t)^3$ is 
$E = Mc^2 + \frac{P}{a} - \frac{3a}{\kappa} (\frac{da}{dt})^2 = 0$
$M$ is the fixed mass of cold matter in the volume, $\frac{P}{a}$ is the decreasing radiation energy in the volume with $P$ constant, and the third term is the gravitational energy in the volume which is negative. The rate of expansion $\frac{da}{dt}$ will evolve in such a way that the (negative) gravitational energy increases to keep the total constant and zero.
For a more general discussion of energy conservation in general relativity see my paper  http://vixra.org/abs/1305.0034
