Depois de instalar o java, parece que o que foi preciso fazer foi o seguinte:

sudo ln -s /usr/lib/jvm/java-7-oracle/jre/lib/amd64/libnpjp2.so /usr/lib/firefox-addons/plugins

A dica veio daqui.

Funcionou do ubuntu 13.4.