Lo primero que vamos a hacer es añadir el repositorio de Oracle a nuestro sistema, así como la clave para validarnos contra dicho repositorio:
sudo echo "deb http://download.virtualbox.org/virtualbox/debian $(lsb_release -sc) contrib" | sudo tee -a /etc/apt/sources.list sudo wget -q http://download.virtualbox.org/virtualbox/debian/oracle_vbox.asc -O- | sudo apt-key add -
Ahora refrescamos nuestro apt-get para que lea los paquetes disponibles en el nuevo repositorio.
sudo apt-get update
Y finalmente instalamos dicho paquete.
sudo apt-get install virtualbox-4.0
Este último paso te desinstalará Virtual Box, si tienes alguno instalado.
Ahora vamos a instalar el paquete de extensiones que añade algunas funcionalidades como el soporte de USB 2.0, entre otros.
wget http://download.virtualbox.org/virtualbox/4.0.0/Oracle_VM_VirtualBox_Extension_Pack-4.0.0-69151.vbox-extpack sudo vboxmanage extpack install Oracle_VM_VirtualBox_Extension_Pack-4.0.0-69151.vbox-extpack
Basado en esta entrada.