Due to past (bad) experience resulting from the GCJ stuff being provided by default on certain distributions, I've always traditionally installed the official Sun Java package on servers.
On Ubuntu it's been easy but now OpenJDK is a preferred option and easier to install... I wonder: is there any reason not to use it instead? As far as I understand it's the open source version of the Sun JDK.
FYI: Sun Java JDK 6u20 (for Ubuntu 10.04) is available from the Canonical Partner repository