Ubuntu11.10で確認
/etc/apt/sources.listの下の2行をコメントアウトを解除
## Uncomment the following two lines to add software from Canonical's
## 'partner' repository.
## This software is not part of Ubuntu, but is offered by Canonical and the
## respective vendors as a service to Ubuntu users.
deb http://archive.canonical.com/ubuntu natty partner
deb-src http://archive.canonical.com/ubuntu natty partner
バージョンが違うubuntuの場合はnattyのとこが違うのかな。
$ sudo apt-get update
$ sudo apt-get install sun-java6-jdk
でインストール。