Antes de começar, certifique-se que possuí uma versão do kernel igual ou maior a 3.10 executando o comando abaixo:

uname -r

Por padrão o Ubuntu 16 deverá possuir uma versão do kernel compatível, não sendo necessário realizar quaisquer outras alterações.

1. Vamos atualizar os pacotes do Ubuntu:

apt-get update
apt-get upgrade

2. Adicione a chave GPG do repositório oficial do Docker em seu sistema:

apt-key adv --keyserver hkp://p80.pool.sks-keyservers.net:80 --recv-keys 58118E89F3A912897C070ADBF76221572C52609D

3. Adicione o repositório do Docker no APT sources:

echo "deb https://apt.dockerproject.org/repo ubuntu-xenial main" | sudo tee /etc/apt/sources.list.d/docker.list

4. Atualize novamente os pacotes para obter os dados do novo repositório instalado:

apt-get update

5. E finalmente vamos instalar o Docker:

apt-get install -y docker-engine

6. Verifique se o Docker foi corretamente instalado e está sendo executado:

systemctl status docker