tmux is two kinds of terminal application: it interacts with your outer, "real" terminal, and it presents an inner, "fake" terminal to the programs running inside it. By default, tmux will respect the limitations implied by $TERM, so if your outer terminal claims to be an 8-colour device, tmux will filter the colours of applications inside it to fit the standard 8-colour palette.
Vim also respects the limitations implied by $TERM, but some people override it into using 256-colour mode anyway, by doing something like "set t_Co=256" in their .vimrc. That works for Vim running in the outer terminal, but it doesn't work for any other tools running in the outer terminal, and in particular it doesn't help tmux.
These days, it's generally best to configure your terminal app to set $TERM to something like "xterm-256color", "nsterm-256color" (for Terminal.app), "putty-256color" (for PuTTY), "gnome-256color" (for libvte-based emulators) or similar. If your terminal application doesn't support manually overriding $TERM, you can do it in your shell profile. That way, every app should understand your terminal's capabilities, including 256-colour support, both inside and outside of tmux.
# Force tmux to assume the terminal supports 256 colors
tmux -2
# if /usr/share/terminfo/x/xterm-256color exists
export TERM='xterm-256color'
# otherwise
export TERM='xterm-color'