Java5 for 32 bit & Java6 for 64 bit Ubuntu

http://source.android.com/source/download.html

The Sun JDK is no longer in Ubuntu's main package repository. In order to download it, you need to add the appropriate repository and indicate to the system which JDK should be used.

Java 6: for Gingerbread and newer
sudo add-apt-repository "deb http://archive.canonical.com/ lucid partner"
sudo add-apt-repository "deb-src http://archive.canonical.com/ubuntu lucid partner"
sudo apt-get update
sudo apt-get install sun-java6-jdk
sudo update-java-alternatives -s java-6-sun

Java 5: for Froyo and older
sudo add-apt-repository "deb http://archive.ubuntu.com/ubuntu dapper main multiverse"
sudo add-apt-repository "deb http://archive.ubuntu.com/ubuntu dapper-updates main multiverse"
sudo apt-get update
sudo apt-get install sun-java5-jdk
sudo update-java-alternatives -s java-1.5.0-sun

To set up your development environment, install the following required packages:
$ sudo apt-get install git-core gnupg flex bison gperf build-essential zip curl zlib1g-dev gcc-multilib g++-multilib libc6-dev-i386 lib32ncurses5-dev ia32-libs x11proto-core-dev libx11-dev lib32readline5-dev lib32z-dev

You might also want Valgrind, a tool that will help you find memory leaks, stack corruption, array bounds overflows, etc.