Eu tive problemas com o openjdk (alguns aplicativos não funcionaram) então estou usando o oracle jdk agora.
Siga o instruções sachin apontou. Você pode continuar a instalá-lo manualmente se realmente quiser ( "o modo manual" na resposta), mas não acho que valha a pena. Basta deslocar-se para "o caminho mais fácil" e é tão simples como:
$ sudo add-apt-repository ppa:webupd8team/java
$ sudo apt-get update
$ sudo apt-get install oracle-java7-installer
(ou oracle-java6-installer para java6 etc)
Vai baixar o pacote oracle e aproveitar para integrar bem o ubuntu.