There are command line tools for calculating ReplayGain values and adding ReplayGain tags. To install the tools for mp3, ogg and FLAC do the following:
sudo apt-get install mp3gain vorbisgain flac
Then to add ReplayGain tags to an album that consists of all files in a directory do the following for mp3:
mp3gain -a *.mp3
For the same task when the album is in ogg vorbis do the following:
vorbisgain -a *.ogg
For the same task when the album is in FLAC files do the following:
metaflac --add-replay-gain *.flac
If you want to add ReplayGain tags to files that are not albums instead use the -r option for mp3gain and vorbisgain (there is no corresponding option for metaflac):
mp3gain -r *.mp3
vorbisgain -r *.ogg
All tools can also be used to remove ReplayGain tags.
As always, make sure you have backups before proceed with any file modification. I have never had problems with these tools but I cannot guarantee they are failsafe (also, your computer could crash or you might have a power outage halfway through the process).