Ubuntu has made it extremely easy to install the Sun Java Development Environment. This is good, because the default java-gcj is very slow.
First install the package with: sudo apt-get install sun-java6-jdk
That may take a while since the package is 125MB. Once it is installed, you still need to make it the default:
sudo update-java-alternatives -s java-6-sun