Mac's always have Java bundled, but for Windows you could bundle your Java Application with Java in a Windows installer, frankly Linux users (who also probably don't have Java installed, though now it's GPL licensed they probably get it bundled too.) should be able to cope.
The basic answer is for OSX: don't. No one wants to download a gigantic file when a tiny one will do. You would need to "bundle" the correct Apple provided Java environment for the OS of the user (not all of them run on all versions of OSX). In addition you would need to check whether Apple and Sun allow redistribution.
As noted above OSX already has Java installed. The correct, supported way to update this install is via Software Update.
Errr...since when? Java installations are trivial in most distros of Linux and I can't think of any reason why anyone wouldn't have it installed (of course...it's not installed by default with some distros...don't get me started on the idiocy of what used to be Ubuntu's Java installation procedure, although again, installs are trivial).