Eu fiz isso para instalar o meu: link
Estou no Ubuntu Maverick.
Existem pacotes demais quando executo apt-cache search java .
Eu fiz isso para instalar o meu: link
Isso deve estar em askubuntu.com, mas para economizar tempo:
sudo apt-get install sun-java6-jdk
Eu acho que está certo. Ele instalará os pacotes extras que você precisa, iirc.
Eu sempre baixo o bin do site sun / oracle e o executo. Eu então uso update-alternatives algumas vezes e isso é tudo.