Update (4/15/2013):
As Thorbj?rn helpfully pointed out, Oracle now has a solution for this. See http://docs.oracle.com/javase/7/docs/technotes/guides/jweb/packagingAppsForMac.html. However, I'm keeping the original content for "historical purposes", and because it was a fun research project.
Previous version (with edits):
This is a great question. I was going to respond that you are simply ahead of your time -- as you pointed out, Java is not going to be removed until the Lion release. However, this article makes it clear that using Java today is not allowed:
Apps that use deprecated or optionally installed technologies (e.g., Java, [PowerPC code requiring] Rosetta) will be rejected.
At the same time, no one has announced a redistributable JRE for Mac OS X yet. I think your best bet, bearing in mind that you are forging new ground, is to check out the Mac OS X Port wiki page of the OpenJDK project. It does describe how to compile your own JDK, but it does not clearly state whether or not the resulting JDK can be "bundled" cleanly or not. I think you will have to try it and see :-(.
Also, it's not clear if the OpenJDK licensing allows this at all (IANAL). Hopefully someone else has already figured this out with regard to Linux/Windows, although of course the rules may be different for the Apple contributions.
Hope this helps. If nothing else, it's a starting point.
EDIT: I am going to throw out one additional suggestion. We now know that Mono apps can be packaged for the App Store. Furthermore, IKVM.NET is a complete implementation of Java that runs on top of Mono. You could try, in theory, to put these two pieces together and get a Java app, bundled for the App Store, that does not in fact require a JRE!
If you try this, I would love to hear how it works out :-).
EDIT 2: Unfortunately, the App Store and the GPL do not appear to be compatible (see http://www.zdnet.com/blog/open-source/no-gpl-apps-for-apples-app-store/8046). The OpenJDK license isn't exactly the same as the GPL, but it's pretty close (again, IANAL). Therefore, Mono & IKVM.NET may be your best bet. Good luck!