You can get themes packages from here: http://www.emacswiki.org/emacs/ColorTheme
The instructions are in README/INSTALL.
Basically, you need to copy all the .el files to a directory in your emacs lisp path. You can
create one in your ~/ and add it to ~/.emacs
(setq load-path (cons (expand-file-name "~/.emacs.d/themes") load-path))
Once you've restart emacs the themes should be available. What you need to do is type:
Alt+x color-theme-select RETURN
You'll get a list of themes that you can try. If you like a theme, place the cursor on a given theme and press 'd' - it will give you the exact name of this particular theme.
To ensure emacs starts with your chosen theme, add the following to ~/.emacs
In this case my theme is called 'deep-blue'