You can get Mplayer and codecs here.
http://www.mplayerhq.hu/homepage/design7/dload.html
There will be a .rpm package for your distro too. Although i have had better luck with Mplayer compiling it myself. the Mplayer packages for FreeBSD seem to work perfectly and no dependency problems.
You might want to upgrade from Redhat 9 to Fedora 3 0r 4 or Centos 4, up to you. They are all Redhat types.
I don't know if you can get a .rpm package for RH9 now. I think that it is no longer supported.
If you decide to conpile it for your self you will need to have gcc and related installed.