For Windows, I suggest using NSIS installer to wrap installation of the JRE and your program. That will allow real "installation", ie. JRE will be installed to Program Files
and it will be possible to uninstall it from Windows control panel ("public JRE"). You need to bundle the JRE installer for that.
Alternatively, you can bundle the whole JRE ("private JRE") together with your program. You can use Launch4J which configures the launch of your Java application (VM options, classpath etc.) as an EXE file, have the JRE somewhere as one of the folders of your distribution and point Launch4J to use it.
Or, simply have the unpacked JRE ("private JRE") in one of the folders of your distribution and use relative paths to use that one instead of the one installed on the system.
The advantage of a private JRE is that you control which Java version it is. With a public JRE, the user may be able to uninstall it or change the version and then come complaining that your program is not working ;)
For Linux, if you distribute you application as an RPM, you can just declare a Java package to be your dependency. Linux package manager should take care of it all. On the other hand, you can still bundle JRE in your own RPM to be independent of the "main" version installed on the user's machine.