Hoy en día el proceso de instalación de java (jdk o jre) es muy sencillo en una distribución Ubuntu cuya versión actual estable es la 8.04 (Hardy Heron). Podemos optar por instlar la version de sun (java-sun) o instalar la versión openjdk (opensource) que ya esta certificada y es totalmente compatible con la versión de sun.
Hay dos formas de hacerlo:
Consola:
Para el ambiente de ejecución. (sun)
sudo apt-get install sun-java6-jre
Para el ambiente de ejecución y el de desarrollo. (sun)
sudo apt-get install sun-java6-jdk
Para el ambiente de ejecución. (opensource)
sudo apt-get install openjdk-6-jre
Para el ambiente de ejecución y el de desarrollo. (opensource)
sudo apt-get install openjdk-6-jdk
Ambiente gráfico:




Y listo !!, tendremos java habilitado y configurado en nuestro Ubuntu.
P.D.
Si no encontraran los paquetes puede ser que no tengan habilitados los repositorios necesarios, para solucionar esto hay que habilitar el repositorio universe ( Menu: Configuración >> Repositorios) y dar click en el botón recargar

Saludos!!