Do Windows XP, Vista, Windows 7 and all Linux distributions have Java JRE installed so end-users don't have to install it to run Java applications?
No, not by default (at least for XP and Ubuntu which I know about).
You have to download and install the Sun version if you want it. It may be that some Linux distros include the GNU Java runtimes.
Not by default, but it's quite easy to install it, and if you want your users not to think about it, you could use launch4j which automatically proposes them a link to the latest JRE.
Many Linux distributions include some form of Java, but you cannot be CERTAIN that a suitable JVM is present for your application.
For Ubuntu installing "sun-java6-jdk" is enough to get all you need as a Java deployer.
Since XP, Windows does not include a JRE (and prior to that, the included JRE was Microsoft's version, not the official Java version, so it always lagged behind and had its own issues).
Many Linux distributions come with a JRE installed, but again it's not the official Java version, since that's closed-source. The latest versions of Ubuntu, openSUSE, and Fedora (among many others) use the JRE from openJDK. It works for a lot of Java programs, but not all of them. A lot of applets and Java programs will crash under it. You can install the official version in Linux from either your distribution's package manager or from the Java website.
In some Linux systems (including Ubuntu), you may need to manually set the official JRE as default in order for the system to use that one without you specifically telling it to do so every time. In Debian-based distributions (including Ubuntu) and openSUSE (and likely others), the command to do this is
sudo update-alternatives --config java and to enable the offical JRE plugin in the web browser is
sudo apt-get install sun-java6-bin sun-java6-plugin.