I tested it out and got it working in the following way:
Install gnome solarized colorscheme. You can get it from https://github.com/aruhier/gnome-terminal-colors-solarized.
Install solarized colorscheme for vim. You can get it from https://github.com/altercation/vim-colors-solarized. In .vimrc you should add following settings:
set t_Co=256 set background=dark colorscheme solarized
Set correct TERM variable by adding following line to your .bashrc/.zshrc
export TERM=screen-256color-bce
Run gnome-terminal, tmux, vim and profit.