Fedora won't ship MP3-capable software because the Fraunhofer Institute's patent license terms are not compatible with the GPL.
The default music player in FC5 is Rhythmbox. I struggled with Rhythmbox for several hours, but despite its pretty face I found it unusable. It ignores track numbers — or, at least, is not as smart at parsing them out of filenames as xmms is, and doesn't document its import rules anywhere. Trying to beat it into playing MP3s is a nightmare so scarifying that at one point I thought I was going to have to reinstall my entire Linux system just to get the ability to play Oggs back, because I couldn't figure out what piece of undocumented application state had gotten scrambled or how to clear it. The documentation is in general a bad joke — glossy, superficial, and with no useful content about troubleshooting problems. The xmms player may not be as featureful or as nice-looking, but it works better.
To install xmms and make it MP3-capable, start by doing this:
yum install xmms xmms-mp3
To actually enable MP3 playing, you'll need to run xmms and change its configuration. Select Options → Preferences → Audio I/O Plugins from the menu; this will pop up a window listing plugins. Select "MPEG Layer 1/2/3 Placeholder Plugin" and uncheck [ ] Enable Plugin. With this placeholder gone, xmms will plug in xmms-mp3 automatically. Kill xmms and restart.
On my x86_64 box I encountered the problem that xmms would only play sound as root, exiting immediately when run from a non-root account. There are a number of mundane causes for this; check the permissions on your sound devices. There is one exotic problem which I tripped over; you may have to tell your sound module to grab low-memory DMA buffers and not let go of them.
To enable MP3 streaming through Firefox or Mozilla, install the gstreamer-ugly plugin and ffmpeg as described below. MP3 streams will play through xmms, podcasts through Totem.