GCJ lets you compile your Java program to a native executable. This can be handy, but this isn't as handy as you might think in relation to generating JVM bytecode.
A GCJ-compiled program starts quickly, and can be used in places where you can't use a JAR file or a shell script wrapper (the two most common choices for launching Java programs), but when you start to execute your generated bytecode, you'll notice that code runs pretty slowly. About the same speed as most interpreters seem to run. This is not a coincidence.
So that's a shame. If you're not generating bytecode, and just using a tree-walking interpreter, this won't be a problem, and you might still want to consider GCJ. Just watch out for GNU Classpath: there are lots of bugs and unimplemented features (including unimplemented features that just silently do the wrong thing), and performance characteristics can be very different. BigInteger, for example, is way slower at the moment.
One idea I haven't yet investigated is that of using GCJ to make a native binary that uses CNI to start Sun's JVM. I'd use GCJ-compiled code to generate the bytecode and hand over to HotSpot for the actual execution. Given that you'd have to pay for the Sun JVM initialization in the end, and you'd miss out on the benefit of having the compiler "warm up" the JVM for execution of the generated code, I'm not sure this would really gain much over just writing a little C++ JNI-based launcher. Maybe start the Sun JVM on another thread while compiling the bytecodes on the main thread?
The start-up time only matters for scripts that take microseconds to execute, because the JVM soon more than makes up the lost time, but it would be nice to have our cake and eat it.