First, run java -version from the command line to show which version you are running.

If you already have Java 1.6 installed

The java executable isn't on your path. Either add Java's bin directory to your PATH, or set the environment variable JAVA_HOME (this should point to the directory above bin), e.g.:

export JAVA_HOME=/usr/lib/j2sdk1.6-sun

If you have Java installed, but it's an old version

Debian Lenny comes with Java 1.5 by default. You need to add non-free to your apt sources, then apt-get install sun-java6-bin and then either update-alternatives --set java /usr/lib/jvm/java-6-sun/jre/bin/java or set JAVA_HOME as per above.

For other distributions, either upgrade your existing version using the instructions below, or install a new private version somewhere else and then set JAVA_HOME as per the instructions above.

If you do not have Java installed

Due to licensing restrictions, some distributions will not have Java directly available in their packaging system. Those that do may have it under "non-free" and it may not be up to date. You need version 1.6.

The simplest way to install Java is to visit http://java.com/getjava and download the latest 1.6 Linux version (32-bit or 64-bit as appropriate) and install it using their installer.

However if you prefer to install it as a package, Debian contains a "java-package" package that will take the file from Sun and turn it into a proper .deb file. NB for Debian 4.0 (etch) or earlier, you will need to make some small manual changes to allow "java-package" to handle Java 1.6 per these instructions.