The Fedora project has dropped MP3 support in their bundled players due to licensing issues. You have a few options:
You could go to:
http://www.xmms.org/download.php and use XMMS to play MP3s. You may need to compile the program itself. You could also try Xine:
http://xinehq.de or MPLayer:
http://mplayerhq.hu
The bundled media players in Fedora only play unrestricted audio formats. It's basically stupid legal issues that are messing with MP3 support. I imagine you have a collection of MP3s you want to play. I would suggest trying one of the above players. If you don't want to compile anything, you could also try:
http://www.real.com and get the latest RealPlayer10 for Linux. It's better than the Windows version because it doesn't load extra programs you don't want and it doesn't blast you with ads. It will play a decent selection of files including MP3 and Ogg Vorbis.
Finally, if you rip your own stuff, you might want to give Sound Juicer a try (comes bundled with Fedora) and rip your music to Ogg Vorbis. It compresses better than MP3 and can be resampled in real time for streaming at a lower bitrate without needing to reencode your files at different bitrates. If you have an MP3 player that you load music onto, then you might want to at least try the FLAC format for archiving on your computer and then convert that to MP3 as needed with the 'lame' utility located at:
http://lame.sourceforge.net/
This isn't a limitation of Linux, it's a limitation of the licensing for MP3. And sadly, money and lawyers make the world go round today...