Here is what I did which seemed to work. I am running Grip 3.07 on Fedora Core 2 so it should be similar to your situation. I do not believe that lame was installed by default and I suspect that it has something to do with patent or copyright issues. Had I thought about it I could have checked by typing 'lame -help' at the command prompt, but instead I just asumed that it was missing and downloaded lame from following location:
http://lame.sourceforge.net/download/download.html
I placed it in my home directory (/usr/local would probably have been better), unpacked and installed it with the commands:
tar xzvf lame-3.96.tar.gz
cd lame-3.96
./configure
make
su root
make install
Within Grip on the config tab I selected the encode menu and changed the encoder to 'lame'. The other options are as follows:
Encoder executable: /usr/local/bin/lame
Encoder command line: -h -b %b %w %m
Encode file format: ~/mp3/%A_%d_%n.mp3 (this puts in in a single directory called mp3 with no subdirectories)
It seems to work fine now. Good luck!
I do like ogg compression better and even went and purchased a HipZip for $40 thinking it would support that format. I haven't had any success yet so I am switching back to the bad ole MP3 format.