The codec works for mplayer (not totem) so you need mplayer, and, if you want, gnome-mplayer so run the following command:
sudo apt-get install gnome-mplayer
It'll pull some dependencies, including mplayer itself.
Then you need to go here and download the tarball for your architecture.
It has a README file, just follow the instructions there, copy the files and your videos should play.