Q:

How to enable AUFS on Debian?

When I try to install docker via:
curl -sSL https://get.docker.com/ | sh

I get the message:

Warning: current kernel is not supported by the linux-image-extra-virtual package.  We have no AUFS support.  Consider installing the packages linux-image-virtual kernel and linux-image-extra-virtual for AUFS support.

However, neither package seems to exist on Debian Jessie:
# apt-get install linux-image-virtual linux-image-extra-virtual
Reading package lists... Done
Building dependency tree
Reading state information... Done
E: Unable to locate package linux-image-virtual
E: Unable to locate package linux-image-extra-virtual

What am I missing here?

A:

aufs is not supported by modern kernels, so you should skip to overlayfs from aufs. Just restart your docker daemon with the option:
--storage-driver=overlay2

(or add this option to /etc/default/docker)
In some systems you should add the processing of the file /etc/default/docker to start procedure by creating /etc/systemd/system/docker.service with content:
[Service]
EnvironmentFile=-/etc/default/docker
ExecStart=
ExecStart=/usr/bin/docker daemon -H fd:// $OPTIONS \
      $DOCKER_STORAGE_OPTIONS \
      $DOCKER_NETWORK_OPTIONS \
      $BLOCK_REGISTRY \
      $INSECURE_REGISTRY \
      $DOCKER_OPTS

More info here
Execute 
systemctl daemon-reload

for changes to take effect.
Caution! All your images become unreachable. If you want to keep them, just save and reload them. You can find the good description here
UPD. I've changed overlay to overlay2 because it solves a little bit more problem than described here
UDP. Not relevant, since overlay2 used by default in modern version of docker (18-06).

A:

Actually installing a stock jessie gives you a kernel that comes with aufs support. My guess is you upgraded to a higher kernel version through jessie-backports which is not not the standard jessie setup. 
This was tested with current Debian jessie 8.7.1 amd64 and kernel 3.16.0.4.
# cat /etc/debian_version
8.7
# dpkg --get-selections | grep linux-image
linux-image-3.16.0-4-amd64          install
linux-image-amd64                   install

# dpkg -L linux-image-3.16.0-4-amd64 | grep aufs
/lib/modules/3.16.0-4-amd64/kernel/fs/aufs
/lib/modules/3.16.0-4-amd64/kernel/fs/aufs/aufs.ko

So to answer your question:
You could re-install Debian Jessie or down-grade to the default kernel and you have a jessie with aufs support. 
For installing aufs on Debian 9 aka Debian stretch one just have to issue an apt-get install aufs-dkms. This is sadly not available for jessie-backports at this time.
At our company we are driving our docker hosts with an jessie aufs setup and everything is running flawlessly.
Update 08-2018
Even now I can not recommend overlay2 for production. We currently have an issue with containers where mysql is not able to create the /var/run/mysqld.sock when running in a container with the overlay2 storage. 
This is addressed in this one year old issue as of August 2018.

