MP3gain changes the gain on each frame in an MP3 making it work across all players that support MP3. It usually also adds an 'undo' APEv2 tag to the MP3 so you change the gain back to normal.
It does not destroy any MP3 data or the like. Replaygain is a very similar solution, except the gain values are kept in tags/LAME header meaning the decoder has to know to look for them, if it doesn't the volume will be unchanged. But this also means it's
completely lossless.
I prefer Replygain for two reasons:
1.) The target loudness is always set to 89 dB, meaning all my files are gained to the same value.
2.)Replaygain is truely lossless, unlike MP3Gain which if you lose the APE tag (which can happen very easily with crappy taggers) there's not way you can get the gain back to its original value.