MpDJ is not involved in this process, but I'm documenting it on this site, because I think it will make things easier. The program I use is called mp3gain. It can be used in a non-lossy or lossy way.

There are two ways I recommend to achieve normalization.

(non-lossy) The first way is to write special tags (replay gain) in the APE or Id3 headers of the file. A compatible player will then pick this up and adjust the sound data on the fly. This is nice because you can re-adjust the volume later and you don't have to worry about loosing quality.
(lossy) The second way is to actually modify the sound data (not the headers) so you can use whatever player you want and not have to worry about tags or other DJ's that use copies of your music. Mp3gain is a tool that can either just add the headers or adjust the files, depending on what parameters you specify on the command line.

Non-Lossy

MpDJ uses MPD as the player. It does support reading the replay gain headers, but only if they are in ID3 form and mp3gain only writes them in ape format.

To use this method here are the steps:

install mp3gain, converter program and that program's dependencies.
run mp3gain on each file. This will write the normalization info in APE format.
run a converter program (ape2id3.py) on each file to convert the APE tags into ID3 tags that MPD can read

These commands assume that your music is the the ~/music folder. Please adjust accordingly.

sudo apt-get install mp3gain
find ~/music -type f -iname '*.mp3' -print0 | xargs -0 mp3gain

wget http://pastebin.com/pastebin.php?dl=f262520f -O ape2id3.py
chmod u+x ape2id3.py
sudo apt-get install python-mutagen
find ~/music -type f -iname "*.mp3" -exec ./ape2id3.py -vd {} \;

Volume normalization must be enabled in MPD. Modify the configuration files (for both the PA system and the headphones system.

gksudo gedit /etc/mpd.conf

# uncomment and set the following properties
replaygain                      "track"
replaygain_preamp               "0"


gksudo gedit /etc/mpd_hp.conf

# uncomment and set the following properties
replaygain                      "track"
replaygain_preamp               "0"

Lossy

This is much easier and strait forward.

sudo apt-get install mp3gain
find ~/music -type f -iname '*.mp3' -print0 | xargs -0 mp3gain -r -k