1) Baixe do site o J2SE Development Kit (JDK):
http://java.sun.com/j2se/1.5.0/download.jsp

2) Va até o diretorio e altere as permissoes do arquivo como root:
sudo chmod +x jdk[nro da versao]

3) Como root copie o arquivo para a pasta /usr/local/
sudo mv /usr/local/

4) Agora instale o JDK como root
sudo ./jdk[nro da versao]

5) Crie, novamente como root, um link simbólico /usr/local/java para apontar para a pasta do jdk na sua maquina:
sudo ln -s /usr/local/jdk[nro da versao] /usr/local/java

Concluida a instalacao, vamos fazer um backup do arquivo .bashrc que fica na sua pasta de usuario:
cp .bashrc .bashrcBackup

Agora podemos configurar as variáveis de ambiente no .bashrc.
gedit .bashrc

Acrescente as seguintes linhas:

JAVA_HOME="/usr/local/java"
JRE_HOME="/usr/local/java/jre"
CLASSPATH="$JAVA_HOME:$JAVA_HOME/lib:$JRE_HOME/lib:."
MANPATH="$MANPATH:$JAVA_HOME/man"
JAVA_DOC="$JAVA_HOME/docs"
PATH="$PATH:$JAVA_HOME/bin:$JRE_HOME/bin"
export JAVA_HOME JRE_HOME CLASSPATH MANPATH JAVA_DOC PATH

OBS: Caso de algo errado resgate o backup do .bashrc (.bashrcBackup)

sudo update-alternatives --config java