I've been using Excelsior Jet since my undergrad thesis. It's free for personal and educational use. It works great. It works directly from the bytecode, so if you can compile your Java code, you can compile your Java code to native code.
I found that it tends to speed things up I think 2 - 4 times, which is nice when your program takes up to a couple hours to run.
Edit (June 7, 2004): Java JRE 1.4.2 has a HotSpot Compiler that does some native code compilation before running (esp. using "java -server"). I haven't done a speed test between the two, but it seems to narrow the gap between "regular" Java execution and with Excelsior Jet.