This was a pain to get working (I use terminal Vim in Linux Mint), and unfortunately I didn't write down the specifics of everything I did. Here is the relevant section of my vimrc:
syntax enable
set background=dark
" colorscheme koehler
set t_Co=16
colo solarized
It may also be worth checking out this project on GitHub.