I recently installed VLC media player, it does a good job. I'm sure mplayer is nice too.
When you get the "E: Package mplayer has no installation candidate" message from Debian, it means that that package doesn't exist in the sources Debian knows about (see /etc/apt/sources.lst). That could be because the package is misspelled, or because the package is, for example, non-free (as in freedom).
What you can do is add a source (repository) to your sources.lst that has the relevant package. For example, see the instructions here:
http://www.videolan.org/vlc/download-debian.html
Don't forget to run "# apt-get update" after changing sources.lst.
Strangely, the VLC repository doesn't have the library package libdvdcss2, so I hunted it down:
Warning: The libdvdcss2 file is used for de-encrypting DVD Zone regions, and may be illegal to use where you live.
What I did after installing VLC and realizing I couldn't get libdvdcss2 from my sources, I added "deb
ftp://ftp.nerim.net/debian-marillat/ sarge main" to sources.lst, then used apt-get update, then installed the library file. I then commented out that source (added a # at the beginning of the line) and did another apt-get update. (All of this as root of course.) This got me the file one time without me having to worry about it being in my sources.lst for future updates.
Do yourself a big favor, and read this:
http://www.debian.org/doc/user-manuals#apt-howto