Follow the instructions here: https://www.linode.com/wiki/index.php/PV-GRUB#Ubuntu_12.04_Precise
Basically:
apt-get update
apt-get install -y linux-virtual grub-legacy-ec2
when prompted, select yes
sed 's/defoptions=console=hvc0/defoptions=console=hvc0 rootflags=nobarrier/g' -i /boot/grub/menu.lst
update-grub-legacy-ec2
then configure Linode profile stuff and reboot.
After that: http://docs.docker.io/en/latest/installation/ubuntulinux/#ubuntu-raring
apt-get install lxc wget bsdtar linux-image-extra-virtual
apt-get update will now be broken for some reason, but you can change the mirrors:
MIRROR=http://mirror.csclub.uwaterloo.ca/ubuntu/
sed 's#http://us.archive.ubuntu.com/ubuntu/#$MIRROR#g' -i /etc/apt/sources.list
sed 's#http://security.ubuntu.com/ubuntu#$MIRROR#g' -i /etc/apt/sources.list
Now we just need to install docker:
apt-get install lxc-docker
@matthewmueller
Very strange! I haven't pinpointed the root cause of the problem yet. The mirrors did indeed fix it for me though.