I understand how photons can change wavelength via gravitational redshifting, but that doesn't seem to be what's going on with the CMB radiation. I've heard it explained as happening because of the expanding universe, but I'm thinking that would have to imply that as the universe expands, lower wavelengths have higher energy, so to conserve energy, the CMB would have to redshift. Is that the case, or is something else going on?
The energy goes nowhere. It needs to go nowhere, since energy conservation only holds for systems which are time translation invariant, and conversation of energy then follows by Noether's theorem.
But the universe, as a whole, is not a time-translation invariant system (or in GR terms, there is no guarantee that we always have the right time-like Killing vectors, see also this old question. You should not expect energy to be in any form conserved on cosmological scales (though in SR, and in suitable subsystems, it is).
CMB photons are redshifted, because the space trough which they travel gets "stretched". You are correct, that this implies, that the accessible universe is "losing" energy in the sense, that one could extract less and less energy from the CMB as more and more cosmological time goes by. It is instructive to imagine a giant "solar array" soaking up all the CMB photons.
Where does this energy go? Assuming that the universe as a whole is energy conserving (that's an assumption for which we lack sufficient experimental evidence, so far), the energy of the photons get converted into an energy term that has to increase the total energy of the "field" that creates spacetime to begin with. We don't have a valid theoretical description for what that "field" is, but energy conservation would tell us something about the time evolution of its energy density and total energy, IF it applies.