Update: There seems to be a simpler way to do this. Take a look at the second comment.

Java 1.6 (also known as Java 6) is now open-source so I installed it on Ubuntu and tried to run Eclipse with it. Unfortunately it said that no compatible java vm was found while searching /usr/lib/j2sdk1.4-sun/bin/java. So I dropped to the command line and tried to run it from there and found out several things:

searching for compatible vm...
  testing /usr/lib/jvm/java-gcj...not found
  testing /usr/lib/kaffe/pthreads...not found
  testing /usr/lib/jvm/java-6-sun...not found
  testing /usr/lib/jvm/java-1.5.0-sun...not found
  testing /usr/lib/j2se/1.5...not found
  testing /usr/lib/j2se/1.4...not found
  testing /usr/lib/j2sdk1.5-ibm...not found
  testing /usr/lib/j2sdk1.4-ibm...not found
  testing /usr/lib/j2sdk1.6-sun...not found
  testing /usr/lib/j2sdk1.5-sun...not found
  testing /usr/lib/j2sdk1.4-sun...not found
Could not create /usr/local/lib/eclipse/.eclipseextension. Please run as root:
    touch /usr/local/lib/eclipse/.eclipseextension
    chmod 2775 /usr/local/lib/eclipse/.eclipseextension
    chown root:staff /usr/local/lib/eclipse/.eclipseextension

First, it was searching in more locations than the dialog box said. Second there seems to be some additional problems related to extensions, fortunately the error message also contained the advice on how to fix it. So first of all I created a symlink to where eclipse was expecting to find java:

sudo mkdir -p /usr/lib/j2sdk1.6-sun/bin
sudo ln -s /usr/bin/java /usr/lib/j2sdk1.6-sun/bin/java

Second, I followed the advice from the error message:

sudo su
touch /usr/local/lib/eclipse/.eclipseextension
chmod 2775 /usr/local/lib/eclipse/.eclipseextension
chown root:staff /usr/local/lib/eclipse/.eclipseextension
exit

And now Eclipse seems to run fine.