Tmux added 24-bit color support in version 2.3. However, the Tmux available in the Ubuntu 16.04 package manager is 2.1 as of October 2017.

You can also read my post covering the steps to compile Vim 8.x on Ubuntu 16.04 to get 24-bit support.

First, check existing version of tmux:

tmux -V

If you see < 2.3, you can easily compile Tmux from source with the instructions below.

Steps to install Tmux from source

Remove existing tmux install:

sudo apt-get -y remove tmux

Install build dependencies:

sudo apt-get install wget tar libevent-dev libncurses-dev

Download from github, untar, and cd to src dir (for a different version, just change the VERSION var):

VERSION=2.6 && mkdir ~/tmux-src && wget -qO- https://github.com/tmux/tmux/releases/download/${VERSION}/tmux-${VERSION}.tar.gz | tar xvz -C ~/tmux-src && cd ~/tmux-src/tmux*

Configure, make, and make install:

./configure && make -j"$(nproc)" && sudo make install

Cleanup:

cd && rm -rf ~/tmux-src

Check version of tmux binary:

tmux -V