MPlayer is my video player of choice. Here is how I install it and set up the codecs:

Install Mplayer from the repositories:

$ sudo aptitude install mplayer

Then, download the codecs package that MPlayer distributes from here. After you download and extract that file, copy the resulting ‘win32′ folder to ‘usr/lib’:

$ sudo cp -R win32 /usr/lib/

Now if you launch mplayer (or gmplayer), it should find those codecs and be able to play most videos.

To play videos embedded in web pages via Firefox, I use mplayer with codecs in conjunction with the MediaPlayerConnectivity extension for Firefox. This extension finds all embedded videos and replaced them with a shortcut that, when clicked, launches the video into your player of choice (mplayer).