So after a few dist-upgrades, docker is not running anymore in my debian Jessie. A quick run of sudo service docker status shows me:

● docker.service - Docker Application Container Engine
   Loaded: loaded (/lib/systemd/system/docker.service; disabled; vendor preset: enabled)
   Active: failed (Result: exit-code) since Wed 2015-09-02 00:03:18 CEST; 8min ago
     Docs: https://docs.docker.com
  Process: 22770 ExecStart=/usr/bin/docker -d -H fd:// $DOCKER_OPTS (code=exited, status=1/FAILURE)
 Main PID: 22770 (code=exited, status=1/FAILURE)

Sep 02 00:03:18 rowanto-mdeb systemd[1]: Started Docker Application Container Engine.
Sep 02 00:03:18 rowanto-mdeb docker[22770]: time="2015-09-02T00:03:18.434820725+02:00" level=error msg="[graphdriver] prior storage driver \"aufs\" failed: driver not supported"
Sep 02 00:03:18 rowanto-mdeb docker[22770]: time="2015-09-02T00:03:18.434912173+02:00" level=fatal msg="Error starting daemon: error initializing graphdriver: driver not supported"
Sep 02 00:03:18 rowanto-mdeb systemd[1]: docker.service: Main process exited, code=exited, status=1/FAILURE
Sep 02 00:03:18 rowanto-mdeb systemd[1]: docker.service: Unit entered failed state.
Sep 02 00:03:18 rowanto-mdeb systemd[1]: docker.service: Failed with result 'exit-code'.

Ops, problem with aufs. A quick fix would be to delete it. You might lose some data, so please do it with care.

sudo rm -rf /var/lib/docker/aufs

After that, just start docker normally

sudo service docker start