Le seguenti indicazioni sono state testate su Debian wheezy, probabilmente su altre distro le cose potrebbero leggermente diverse ma comunque l'essenza non cambia.
 

Installazione OpenJDK

Seguendo le istruzioni su http://openjdk.java.net/install/ risulta che per installare la versione 7 di OpenJDK è sufficiente lanciare il seguente comando da terminale:

sudo apt-get install openjdk-7-jre

​Installazione JDK/JRE Oracle

​Siccome non vengono più rilasciati pacchetti .deb per la Virtual Machine Oracle di Java, è necessario scaricare il binario direttamente dal sito del produttore, che però andrebbe installato a mano.
Per ovviare il problema ed avere ugualmente un pacchetto .deb da gestire direttamente con apt è possibile utilizzare JavaPackage.
JavaPackage si occupa di convertire il file scaricato dal sito di Oracle in un .deb.

Aprite un terminale e controllare nel sources.list sotto /etc/apt che ci sia una riga tipo questa

deb http://ftp.it.debian.org/debian wheezy main contrib

Per visualizzare il contenuto del file è possibile utilizzare il classico

$ cat /etc/apt/sources.list

Se avete modificato il sources.list dovete aggiornare la lista pacchetti

$ sudo apt-get update

Ora possiamo installare java-package

$ sudo apt-get install java-package

Scarichiamo la versione di jdk/jre desiderata (32 o 64 bit) dal sito del produttore.
Una volta scaricato possiamo lanciare il programa che si occuperà di creare il .deb.
Utilizzando un utente non root spostarsi nella cartella in cui si è scaricato il .tar.gz scaricato e lanciare il comando

$ make-jpkg jdk_equalcosa.tar.gz

Possiamo ora installare il file .deb creato

$ sudo dpkg -i oracle-j_equalcosa.deb

Ora possiamo selezionare la versione di java che preferiamo utilizzare di default

$ sudo update-alternatives --auto java