Esta guía sirve para cualquier distribución de las que pongo aquí abajo el repositorio:

Ubuntu / Kubuntu Feisty Fawn    ->    deb http://www.virtualbox.org/debian feisty non-free
Ubuntu / Kubuntu Edgy Eft         ->    deb http://www.virtualbox.org/debian edgy non-free
Ubuntu / Kubuntu Dapper Drake  ->    deb http://www.virtualbox.org/debian dapper non-free
Debian Etch                               ->    deb http://www.virtualbox.org/debian etch non-free
Debian Sarge                             ->    deb http://www.virtualbox.org/debian sarge non-free

Bueno lo primero que haremos será añadir el repo a nuestro sources.list, añadiremos la línea en función de la distribución que usemos, en mi caso en este momento Debian Etch en su rama testing. Vamos al meollo, abrimos el sources:

sudo kate /etc/apt/sources.list

y añadimos la línea:

deb http://www.virtualbox.org/debian etch non-free      //este es mi caso debian etch, pero el tuyo puede ser otro, coge el que te corresponda de la lista de arriba.

Después hay que añadir la key, primero descargarla, así que vamos al lío:

wget http://www.virtualbox.org/debian/innotek.asc
sudo apt-key add innotek.asc            // tiene que dar como respuesta un OK
rm innotek.asc                                // una vez añadida no la necesitamos para nada

Una vez hecho todo esto ya estamos listos para instalar VirtualBox:

sudo apt-get update
sudo apt-get upgrade                       // Esto lo haremos siempre que añadamos un repo
sudo apt-get install virtualbox

Durante la instalación nos pide añadir nuestro usuario a /dev/vboxdrv, esto lo hacemos mediante este comando:

sudo usermod -G vboxusers -a usuario

Pues ya tenemos instalado VirtualBox, además desde repositorio, jejej.

Solución a posible problema:

Es posible que despues de instalarlo al arrancar un sistema emulado, nos aparezca un error VBox status code: -1909 VERR_VM_DRIVER_NOT_ACCESSIBLE, esto lo arreglaremos con:

sudo chmod 666 /dev/vboxdrv