In order to add mp3 functionality to my RHEL 4.0 workstation, I had to install these rpms:
lame-3.96.1-0.lvn.1.4 gstreamer-plugins-mp3-0.8.8-0.lvn.1.4
Now rhythmbox will play my mp3s.