Então, o problema aqui foi que eu precisava rodar:
sudo apt-get update
Em seguida, execute o comando:
sudo apt-get install sun-java6-jre
funciona! Porém, você será solicitado a aceitar o contrato do usuário. Eu estou usando o Windows e Putty e não foi de todo claro como aceitar isso (clicando em OK não funciona). Eu tive que apertar a aba até que fosse destacada.
Isso finalmente pareceu funcionar.