Duas coisas: eu não uso a versão OSE porque ela tem restrições em relação à versão 3.x (uma delas, se não me engano, é que a OSE não permite acesso a USB).
Então, ao invés de baixar direto do site do VirtualBox, como o Platão sugeriu, prefiro adicionar, nos Canais de Software e, desta forma, instalar diretamente através do Synaptic. A vantagem desta alternativa é que as atualizações podem ser instaladas de forma automática, como um pacote normal do Ubuntu.
Para adicionar nos Canais de Software, eu faço o seguinte:
-- no terminal, eu entro com o comando
wget -q http://download.virtualbox.org/virtualbox/debian/sun_vbox.asc -O- | sudo apt-key add -
-- na opção Sistema > Administração > Canais de Software, escolho a aba Outro Software e opção Adicionar.
-- no campo linha do APT, insiro o seguinte:
deb http://download.virtualbox.org/virtualbox/debian jaunty non-free
(trocando "jaunty" pela versão do Ubuntu que estou usando. P.ex., se for a 10.04, eu coloco "lucid").
-- aí, é só clicar em Fechar e a seguir em Recarregar.
A partir daí, você pode instalar o VirtualBox através do Synaptic.