I installed Java 6 on a Strato V-Server today that a default installation of Ubuntu 8.04 LTS.
Per default, the multiverse packages are all disabled, so you need to edit the file /etc/apt/sources.list to make it look like this:

# See sources.list(5) for more information, especialy
# Remember that you can only use http, ftp or file URIs
# CDROMs are managed through the apt-cdrom tool.

deb ftp://ftp.stratoserver.net/pub/linux/ubuntu hardy main restricted universe multiverse
deb-src ftp://ftp.stratoserver.net/pub/linux/ubuntu hardy main restricted universe multiverse

deb ftp://ftp.stratoserver.net/pub/linux/ubuntu hardy-updates main restricted universe multiverse
deb-src ftp://ftp.stratoserver.net/pub/linux/ubuntu hardy-updates main restricted universe multiverse

deb ftp://ftp.stratoserver.net/pub/linux/ubuntu hardy-security main restricted universe multiverse

deb-src ftp://ftp.stratoserver.net/pub/linux/ubuntu hardy-security main restricted universe multiverse

Then don’t forget to run

sudo apt-get update
sudo apt-get upgrade