Where does the energy go when light is redshifted? Imagine a galaxy millions of lightyears away and, obeying Hubble's law, moving very quickly away from us. 
Now imagine the same galaxy emitted a green photon in our direction (a photon with a frequency of $f_g$.) That photon reached earth, due to the redshift, with a frequency $f_r$, with $f_g>f_r$. That means photon $f_g$ left the distant galaxy with an energy of $H_g=hf_g$, but when it reached Earth, it had an energy of $H_r=hf_r$.
But  $H_r < H_g$, so where did the difference between the energies go?
 A: Nobody ever said that different observers have to agree on the energy of a photon (or anything else).  The invariant quantity is energy squared minus momentum squared  (i.e. rest mass), which is equal to zero whether the photon is red or green.  (Edited to add:  I see now that userLTK already said as much in a comment.)
A: 
Where does the energy go when light is redshifted?

It doesn't go anywhere. Let's say we're motionless with respect to some source which is emitting a stream of photons. We agree that the photons have some energy E=hf. Now let's say I push you such that you're moving away from the source. You now claim that the photons are redshifted, but those photons haven't changed one jot. Instead you have. I did work on you, I added energy to you. The photon energy hasn't changed, but yours has, so your measurement of the photon energy has reduced. You might say you're going faster than you were, so you measure the selfsame photon energy as reduced. Even though it hasn't, because conservation of energy applies.  
It's similar for gravitational redshift$^*$. Let's say we're down on the ground near some source which is emitting a stream of vertical photons. We agree that the photons have some energy E=hf. Now let's say I lift you up away from the source. You now claim that the photons are redshifted, but those photons haven't changed one jot. Instead you have. I did work on you, I added energy to you. The photon energy hasn't changed, but yours has, so your measurement of the photon energy has reduced. At the higher elevation there's less gravitational time dilation. Your clocks are now going faster than they were, so you measure the selfsame photon energy as reduced. Even though it hasn't, because conservation of energy applies.  

Now imagine the same galaxy emitted a green photon in our direction (a photon with a frequency of fg). That photon reached earth, due to the redshift, with a frequency fr... where did the difference between the energies go?

It didn't go anywhere. Your and your clocks are now going faster than they were, so you measure the selfsame photon energy as reduced. Even though it hasn't, because conservation of energy applies.  
$*$ And blue shift. Throw a 511keV photon into a black hole and the mass increases by 511keV/c². Conservation of energy applies. 
