In addition to the bundle-the-jre option (which is extremely workable), you can also feed java bytecode into robovm [1], which spins it through LLVM and produces native binaries for any platform you can go with LLVM. (Most of the documentation emphasizes IOS, but speaking from experience, yes, you absolutely can make mac desktop and linux native binaries as well.)
What robovm can do is a great example of the joys of toolchains with a well-defined stable intermediate representation. (Or one of the joys, I should say -- the flowering of languages on top of the jvm is another.)
Go's first-class AST work is excellent stuff, but I'd love it even more if they fleshed out a well-defined, stable, portable intermediate format like LLVM's IR and java's bytecode. Making a release of software and knowing it can run on architectures you haven't even thought of yet is liberating. Sure, architectures don't come along "very often" (but they're starting to happen more often!), and sure, you can use a full vm at the bottom layer (but it's slow! It can't do a fraction of the optimizations possible with an IR/bytecode), and sure, you can just pretend the source is an IR (but if some library you use chooses a different build tool chain than you, you're going to have a bad time -- don't laugh, golang is too young to have bifurcated much yet, but give it time, and look at what happened around the go-get mess already; or, consider what happens when someone just adds more tooling like source generation, which has also already happened)... Taking the long view, I think an intermediate representation has proven incredibly useful for the jvm as a platform, and I hope golang also grows to offer such a route sometime in the future.
[1] http://robovm.com/