sudo apt-get remove openjdk-6-jre-headless sun-java6-bin sun-java6-jre
É claro que também removerá todos os pacotes que dependem de um pacote JRE. Se você quiser usá-los, você precisará criar um pacote JRE fictício, com equivs
.
Portanto, é provavelmente mais fácil deixar um JRE empacotado instalado.