Com minha experiência com o openjdk não é muito bom (acho que é ainda pior do que o próprio Java), então eu não gosto de Java, mas se você quiser instalá-lo, eu recomendo que você o instale com este guia
$ sudo apt-get install openjdk-7-jre
[sudo] password for paul:
Reading package lists... Done
Building dependency tree
Reading state information... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:
The following packages have unmet dependencies:
openjdk-7-jre : Depends: openjdk-7-jre-headless (= 7u25-2.3.10-1ubuntu0.13.04.2) but it is not going to be installed
Depends: libgif4 (>= 4.1.4) but it is not installable
Depends: libatk-wrapper-java-jni (>= 0.30.4-0ubuntu2) but it is not installable
Recommends: libgnome2-0 but it is not installable
Recommends: libgnomevfs2-0 but it is not installable
Recommends: libgconf2-4 but it is not installable
Recommends: ttf-dejavu-extra but it is not installable
E: Unable to correct problems, you have held broken packages.