Linux Mint 14
I solved the problem combining Jerome's and Jarod's answer:
sudo apt-get install openjdk-7-jdk
sudo nano /etc/environmentadding the following line:
Also I just found http://stackoverflow.com/a/17827697/2533809 which seems to have a nice write-up, pretty much the same answer.
(I'm using Debian 7 Wheezy)