From the README (emphasis mine):
IMPORTANT NOTE FOR TERMINAL USERS:
If you are going to use Solarized in Terminal mode (i.e. not in a GUI
version like gvim or macvim), please please please consider
setting your terminal emulator's colorscheme to used the Solarized
palette. I've included palettes for some popular terminal emulator as
well as Xdefaults in the official Solarized download available from
[Solarized homepage]. If you use Solarized without these colors,
Solarized will need to be told to degrade its colorscheme to a set
compatible with the limited 256 terminal palette (whereas by using
the terminal's 16 ansi color values, you can set the correct, specific
values for the Solarized palette).
If you do use the custom terminal colors, solarized.vim should work
out of the box for you. If you are using a terminal emulator that
supports 256 colors and don't want to use the custom Solarized
terminal colors, you will need to use the degraded 256 colorscheme.
To do so, simply add the following line before the colorschem solarized
line:
let g:solarized_termcolors=256
Again, I recommend just changing your terminal colors to Solarized
values either manually or via one of the many terminal schemes
available for import.
Simply selecting Solarized for both "Text and Background Color" (choose light or dark) and "Palette" in Terminal → Preferences → Profiles → (select yours) → Edit → Colors worked for me on Ubuntu 16.04 (Xenial Xerus) with the included Terminal application.
Some other answers recommend choosing a 256 color palette but, as mentioned in the documentation, this gives you a degraded (and visibly worse in my opinion) color scheme.