Das Problem hier war also, dass ich laufen musste:
sudo apt-get update
Dann den Befehl ausführen:
sudo apt-get install sun-java6-jre
funktioniert! Sie werden dann aufgefordert, die Benutzervereinbarung zu akzeptieren. Ich verwende Windows und Putty und es war überhaupt nicht klar, wie man das akzeptiert (das Klicken auf OK funktioniert nicht). Ich musste Tab drücken, bis es hervorgehoben wurde.
Das schien endlich zu funktionieren.