Esta instalação foi realizada no Ubuntu 9.10, provavelmente deve funcionar para a versão 9.04 também. O processo de instalação na verdade é mais cansativo do que complicado, precisa de uma conexão razoável para baixar todos os pacotes.
Então vamos começar removendo pacotes não utilizados:
sudo apt-get autoremove
Instalando as dependências:
sudo apt-get -y install tcsh git-core scons g++
sudo apt-get [...]

Depois de muito tempo sem postar no Ubuntu Brasil segue o primeiro tutorial de 2010.

Instalando VirtualBox dos binários Precompiled
Abra primeiramente um terminal (aplicações > acessórios > terminal):
Abra /etc/apt/sources.list..
gedit /etc/apt/sources.list do sudo
E adicione o repositório de VirtualBox:
deb http://download.virtualbox.org/virtualbox/debian
Adicione então a chave pública do repositório de VirtualBox a seu sistema…
wget – q http://download.virtualbox.org/virtualbox/debian/sun_vbox.asc – o | [...]