It looks like you have installed the wrong docker..
apt-get install docker will a install a "System tray for KDE3/GNOME2 docklet applications"
Installing lxc-docker will get you the package to "create lightweight, portable, self-sufficient containers from any application."
I had the same issue "Segmentation Fault or Critical Error encountered. Dumping core and aborting." following these instructions (as root) : https://www.linode.com/docs/applications/containers/how-to-install-docker-and-deploy-a-lamp-stack
However @xianlinbox 's solution does not work on my machine* :
$ sudo apt-get install docker.io
(* My machine is a Linode server running Ubuntu 12.04 - it is an old Ubuntu, and it is also a custom distro I believe - I've decided the easiest solution for me will be to find a different host)