Du kan ju testa följande (som root)

apt-cache search java |more

för att se vad det finns för olika installerbara java att välja mellan

sen

apt-cache show "det paket du vill veta mer av" ex.

apt-cache show sun-java6-jre

Där ser du om det är installerat eller inte, är det installerat står det "Status: install ok installed"

När du hittat det java du vill ha bort är det bara och köra

apt-get --purge remove "ditt paket du vill ha bort"

Inte det smidigaste kanske, och det underlättar om du vet exakt vad javapaketet som är installerat heter. Annars är det nog smidigare att köra någon sorts installationshanterare där du kan söka och få mer överblick.