Por conta do Java ter sido proibido de ser redistribuído nos DVDs de Linux só nos sobrou duas alternativas, usar o OpenJDK (que não funciona a contento) ou voltar ao tempo das cavernas do sistema Linux quando tínhamos que instalar a JRE na munheca. Visando facilitar este trabalho eu estou disponibilizando um script que usava naquela época (obviamente já devidamente atualizado) e que baixa, instala e configura os links para que você tenha a última versão do JRE corretamente funcional em seu ambiente Ubuntu / Debian. Baixe-o, dê permissão de execução, execute-o como root e seja feliz.