Eu acho que isso é o que você quer. Execute o seguinte comando no Terminal.
sudo apt-get install openjdk-7-jre
Dica rápida
Quando você está procurando por um programa como este, tente o seguinte comando:
apt-cache search keywords here
Então, por exemplo,
apt-cache search jre 7
Dá isto:
icedtea-7-jre-jamvm - Alternative JVM for OpenJDK, using JamVM
openjdk-7-jre - OpenJDK Java runtime, using Hotspot JIT
openjdk-7-jre-headless - OpenJDK Java runtime, using Hotspot JIT (headless)
openjdk-7-jre-lib - OpenJDK Java runtime (architecture independent libraries)
openjdk-7-jre-zero - Alternative JVM for OpenJDK, using Zero/Shark
Você pode então usar o bom senso para descobrir qual pacote instalar.