Originally Posted by dandart
All players will offer to install extra codecs when they need it.
That's entirely distro dependent. I think that ubuntu does that. But players don't have that functionality builtin. At least not if you use vanilla builds as upstream offers them. The kind of codecs that a given package will support are defined during the compilation of the package most times. At least it's that way for mplayer, vlc and xine. However in binary distros this can be conditioned by 3rd party package like ffmpeg or libavcodec, which can be installed or not.
Some people will suggest you to install win32codecs for mplayer, which I think it's useless nowadays. Mplayer supports natively almost anything you can dream of.