Você precisa ativar a origem do parceiro (supondo que esteja usando o Lucid):
sudo add-apt-repository “deb http://archive.canonical.com/ lucid partner”
Atualize e instale os pacotes necessários:
sudo apt-get update
sudo apt-get install sun-java6-jre sun-java6-jdk sun-java6-plugin sun-java6-fonts