Every user of my game would require the JRE? How would I go about giving them that? I feel like there should be some easier way :/
That's the nature of Java. When you compile a Java program, you are not creating a native executable, but rather a collection of bytcode that is intended to be executed by a virtual machine. The JRE is the standard runtime environment (including the Hotspot VM), so is perhaps the most commonly available. But there are others across a variety of platforms.
Though you will find a JRE on a large percentage of systems, not all will be the version you require. If you are using Java 7 features, for example, then someone with a version 6 JRE will not be able to execute your program without updating. There are several ways around that. The easiest, and I would speculate the least effective, would be to provide a link to the JRE download page on your game's download page. If this is just a project that you're doing for fun, it won't really hurt anything.
If you want to be serious about it, one common approach I've seen Java game developers, like Puppygames, take is to just include a private JRE in the game's installation and provide a shell script, or a small C or C++ executable, that launches it. Cas from Puppygames detailed how he does it in a post at JGO not long ago, if you want to search for it.
Additionally, there are programs out their that can package your Java apps up into a native executable configuration for you, though they vary in how they go about it. The one ChaosEngine linked above, Excelsior Jet, provides an AOT compiler that compiles everything into a native executable before the program is run (much like a C or C++ program), but it's rather expensive. Then there's Launch4j, which is free. It's a tool that launches Java apps according to a specific configuration. It can be configured to search for a specific Java version on the user's machine, or to work with a privately bundled JRE (in other words, bringing some automation to the process I described in the previous paragraph). There are similar tools to be found if you look.
So there are definitely options. I can't recommend one over another, though, as I've never used any of them myself.