How do I install Docker on Ubuntu 16.04 LTS?

Docker comes in two flavours: The Comunity Edition (CE) and the Enterprise Edition (EE). See this question for the differences. Just take Docker CE if you don't know which to take.

There are two ways of installing it (thank you, Katu and Suor!). The official docker way is a bit more recent.

(A) Official Ubuntu Repositories

$ sudo apt-get install docker.io

In the past this way was discouraged as the docker package was super outdated. The universe sources are fairly recent now.

(B) Official Docker Way

The Ubuntu installation instructions list all you need in detail, but in most cases it boils down to:

(1) Set up the docker repository

sudo apt-get update
sudo apt-get install apt-transport-https ca-certificates curl software-properties-common
curl -fsSL https://download.docker.com/linux/ubuntu/gpg | sudo apt-key add -
sudo add-apt-repository "deb [arch=amd64] https://download.docker.com/linux/ubuntu $(lsb_release -cs) stable"

(2) Install Docker CE

sudo apt-get update
sudo apt-get install docker-ce

(3) Verify the installation

sudo docker run hello-world

The latest version can be found here. It was 18.06 in November 2018. This version is available in the sources from above, whereas the default Ubuntu package sources only contain Docker 1.5 (source). You can find changes in the docker release notes. Version 1.5 is so old that I could not find out how old it is.

To install the Ubuntu repository version

sudo apt install docker.io

Check the version with

docker --version

You may still want to do the post-install steps. Thanks @wisbucky