Looking at the normailze uttilty, it says it can normalize a mp3 w/o having to re-encode the whole file. Says: "If you use an mp3 player other than xmms, you'll have to bug the author to support RVA2 frames in ID3 tags."
Oh great, another standard. See various comments on the Karma BBS for why ReplayGain got pulled from Karma (and thus car-player v3).

There is a program called mp3gain, which doesn't "re-encode" the whole file, but just frobs with the MP3 format's per-packet gain field to produce the same effect. That is currently your only way of getting RG on the car-player, and then only for MP3.

Peter