You should be able to use an HQ bundle download that contains a JRE for use with HQ. Look for x86-linux or x86_64-linux, and you should be golden. If you would prefer to work with the noJRE bundle, having downloaded and installed your own JRE, you would want to set HQ_JAVA_HOME or JAVA_HOME to the path for that JRE (HQ will use its bundled JRE by default, so no need to set the paths in that case).
I could not find reference to a valid Sun JRE package when quickly searching for one, but I believe that `apt-get install sun-java5-jdk` will install the JDK, and that can also be used. I don't have immediate access to an Ubuntu machine at present, so if that fails to work, I can probably run-down more information a bit later.