If you just need MP3 support, you might want to start here. Otherwise, I recommend using Livna.org's MPLayer package with the codecs found at http://www.mplayerhq.hu.
Install Livna's release package for Fedora 9. This will provide you with access to Livna.org's Fedora 9 YUM repository using /etc/yum.repos.d/livna.repo.
rpm -ivh http://rpm.livna.org/livna-release-9.rpm
Install mplayer from Livna.org.
sudo yum -y install mplayer
Now, visit the MPlayer Codecs Directory and download the latest 'All' tarball.
wget http://www.mplayerhq.hu/MPlayer/releases/codecs/all-20071007.tar.bz2
Next, prepare the codecs folder. MPlayer from Livna.org will use /usr/lib/codecs.
sudo mkdir -p /usr/lib/codecs
Other media players like Xine and avifile might use /usr/lib/win32, so create a symlink.
sudo ln -s /usr/lib/codecs /usr/lib/win32
ls -l /usr/lib/win32
lrwxrwxrwx 1 root root 15 2008-05-24 08:02 /usr/lib/win32 -> /usr/lib/codecs
Finally, extract the contents of the tarball and copy all files to /usr/lib/codecs.
tar -xjvf all-20071007.tar.bz2
sudo cp -a all-20071007/* /usr/lib/codecs/
See the MPlayer(1) man page for /usr/bin/mplayer usage.
man 1 mplayer