I usually just install all(both video and audio) codecs from mplayer's site. This works for both mplayer and xine-based players(including the popular amarok music player).
First download the latest all package here:
http://www.mplayerhq.hu/MPlayer/rele...060611.tar.bz2
Become root (su
Next just copy and paste this:
mkdir /usr/local/lib/codecs/
mkdir /usr/lib/win32
tar xvfj all-20060611.tar.bz2
cp ./all-20060611/* /usr/local/lib/codecs/
cp ./all-20060611/* /usr/lib/win32/
chmod 755 /usr/local/lib/codecs/*
chmod 755 /usr/lib/win32/*
...as you can see, all codecs will be installed in both "usr/local/lib/codecs/ (new mplayer way) and "/usr/lib/win32/" (old mplayer/xine way).
I personally prefer MPLayer as my video player. Xine is an excellent video player/engine as well and uses the same codecs.
An other popular player/engine is VLC(doesn't use the same codecs):
http://www.videolan.org/
For all xine-based music players (many of them like amarok can actually use more than one engine), the above codecs will work as well.
Some stand alone music players like xmms and beep need an extra mp3 package if the player came with your distro (xmms-mp3).