El paquete docker ya dentro de Ubuntu se llama docker.io [1] así que hazlo
sudo apt-get install docker.io
Pero si sigue el enlace que proporcionó y realiza los pasos 7, 8, 9, luego su instalación sabrá sobre el paquete en el repositorio de Docker y también encontrará docker-engine .
Tu llamada. Ejecuto la versión de Ubuntu (actualmente 0.11.2 en Ubuntu 16.04) en algunas máquinas y la de Docker en otras (ya que tenía curiosidad sobre algunas características de 0.12). Ambos funcionarán bien.
[1] Como docker se utiliza para los iconos de 'acoplamiento' de una aplicación de inicio de escritorio.