1) Em /etc/apt/sources.list, colocar as linhas de repositórios abaixo:

  deb http://antesis.freecontrib.org/mirrors/ubuntu/plf/ breezy free non-free

  deb-src  http://antesis.freecontrib.org/mirrors/ubuntu/plf/ breezy free

2) Dar update: $ sudo aptitude update

3) Instalar o java : $ sudo aptitude install sun-j2re1.5

Outra referência: http://www.linuxdailylog.com/2005/10/instalando-o-java-1505-no-ubuntu-510.html