Como todos sabéis, en Ubuntu, por defecto, el soporte para aplicaciones Java viene provisto por el OpenJDK, una implementación libre del JDK. Sin embargo el SDK de Android no es compatible con éste por lo que es necesario recurrir al JDK "original" de Oracle. Hace un tiempo Oracle retiró las licencias de "Distribuidor de Java" lo que obliga a Ubuntu a retirar los paquetes del OracleJDK de sus repositorios, por lo que ahora mismo la instalación de esta herramienta dista mucho de seguir el proceso automático al que nos tiene acostumbrados la instalación de aplicaciones en Ubuntu.
Existen muchos tutoriales en Internet sobre como instalar Java en Ubuntu, pero cada uno propone una forma distinta de hacerlo: utilizar repositorios Java alternativos mantenidos por terceros, usar scripts que automaticen ciertas tareas o configurarlo todo a mano incluyendo los archivos de configuración de bash. A continuación voy a detallar los pasos que he seguido yo desde cero hasta poder ejecutar mi primera aplicación en un emulador Android, creo que estos pasos son los más sencillos y fáciles para instalar y configurar todo y además... funcionan

Nota: el SDK de Android solo está disponible en versión 32bits por lo que si usamos Ubuntu 64bits tendremos que descargarnos la librería ia32-libs
apt-get install ia32-libs
1. Instalando OracleJDK:
En primer lugar nos dirigimos a la página oficial de Oracle Java para descargarnos el JDK. Nos descargaremos la versión 6 ya que, en la fecha en que se escribe este post, la versión 7 se encuentra en estado alpha por lo que no se recomienda su uso y dudo que esté completamente soportada por Android. Yo concretamente he descargado el JDK para Java SE 6 Update 30 para Linux 32 bits y formato binario autoextraíble (cuidado: elegir el que no pone rpm).

A partir de aquí lo haremos todo con consola así que Ctrl+Alt+T y a teclear. Nota: sustituir XX por la versión que hayas descargado.
En primer lugar nos dirigimos a la carpeta donde se haya descargado el archivo, por defecto debería ser Descargas
cd Descargas
Damos permisos de ejecución al archivo
sudo chmod +x jdk-6uXX-linux-i586.bin
Y nos lo llevamos al directorio donde queramos descomprimirlo, yo lo he puesto en /usr/lib/jvm/ que es donde se encuentra todo lo relacionado con Java en Ubuntu
sudo mv jdk-6uXX-linux-i586.bin /usr/lib/jvm/
Lo ejecutamos para que se autoextraiga, es posible que durante este proceso se nos pida que aceptemos la licencia de Java
sudo ./jdk-6uXX-linux-i586.bin
Ahora se nos ha creado un nuevo directorio que contiene todas las herramientas del JDK de Oracle. Más información sobre este directorio y su estructura aquí http://docs.oracle.com/javase/6/docs/technotes/tools/linux/jdkfiles.html. Para ahorrar espacio podemos borrar el binario
sudo rm jdk-6uXX-linux-i586.bin
Ahora necesitamos decirle a Ubuntu que hay nuevas herramientas disponibles y que queremos que use éstas en lugar de las que usaba antes. Para decirle que hay una nueva herramienta llamada java usamos este comando
sudo update-alternatives --install "/usr/bin/java" "java" "/usr/lib/jvm/jdk1.6.0_XX/bin/java" 1
Y para decirle que queremos que use esta nueva herramienta por defecto en lugar de la que usaba anteriormente del OpenJDK
sudo update-alternatives --set java /usr/lib/jvm/jdk1.6.0_XX/bin/java
Hacemos lo mismo para el compilador javac
sudo update-alternatives --install "/usr/bin/javac" "javac" "/usr/lib/jvm/jdk1.6.0_XX/bin/javac" 1
sudo update-alternatives --set javac /usr/lib/jvm/jdk1.6.0_XX/bin/javac
Realmente OpenJDK no implementa una herramienta javac para compilar sino que se basa en el gcj por lo que solo con el primer comando bastaría, ya que al no existir otra herramienta llamada javac Ubuntu usará ésta (la única que hay con ese nombre) por defecto, pero tampoco perdemos nada por asegurarnos.
Podemos comprobar que todo funciona correctamente tecleando
java -version
javac -version
En la salida del primer comando tenemos que fijarnos que la versión que aparece coincida con la que acabamos de instalar y a demás que no aparezca nada de OpenJDK, así nos aseguramos de que estamos usando el java de Oracle. El segundo comando arrojará una salida mucho más simple (simplemente el número de versión) pero basta para saber que funciona y puesto que no hay otra herramienta con el mismo nombre sabemos que estamos usando la correcta.
Solo nos quedaría por configurar el plugin java para el navegador, pero IcedTea, el que ofrece OpenJDK, me funciona perfectamente y puesto que no es necesario para Android prefiero dejar las cosas como están.
2. Instalando Eclipse:
Utilizaremos Eclipse como herramienta principal para desarrollar en Android básicamente porque existe un plugin oficial de Android para este IDE que nos facilitará mucho las cosas.
Podemos descargar la última versión de Eclipse desde los repositorios de Ubuntu, pero al mirar las dependencias vemos que toca muchos paquetes relacionados con OpenJDK y después de tener java perfectamente configurado no creo que nos queramos arriesgar a que el gestor de paquetes nos pise toda esa configuración, así que nos dirigimos a la página oficial de descargas de Eclipse http://www.eclipse.org/downloads/, arriba a la derecha indicamos que usamos Linux y nos descargamos la versión para 32 bits de Eclipse Classic que es el recomendado por Android.
Obtenemos un archivo comprimido que podremos extraer donde queramos. Yo me he creado una carpeta "Aplicaciones" dentro de mi carpeta personal y lo he extraído ahí dentro, lo cual crea un directorio llamado "eclipse" dentro del cual encontramos el ejecutable que arranca el programa.
Al arrancar se nos pedirá que indiquemos la localización del workspace, el directorio donde se almacenarán nuestros proyectos. Yo dejo el que viene por defecto, en la carpeta personal, y le digo que no me vuelva a preguntar.
3. Integrando Eclipse en Unity:
Al no haber instalado Eclipse, solo lo hemos descomprimido y ejecutado, la integración por defecto con Unity es pésima: no aparecerá el icono correctamente en la barra lateral y no podremos encontrarlo dentro de las aplicaciones en el menú Inicio.
La integración de las aplicaciones con Unity se lleva a cabo a través de un archivo .desktop que sigue el estándar definido por la organización freedesktop. En Ubuntu estos archivos se localizan en /usr/share/applications/ así que en la consola tecleamos
sudo gedit /usr/share/applications/eclipse.desktop
Y escribimos las siguientes líneas
[Desktop Entry]
Name=Eclipse
Comment=Entorno de desarrollo integrado Eclipse
Exec=/home/usuario/Aplicaciones/eclipse/eclipse
Icon=/home/usuario/Aplicaciones/eclipse/icon.xpm
Terminal=false
Type=Application
Categories=Development
Por supuesto en Comment puedes poner lo que quieras y en Exec y Icon debes poner la ruta al directorio donde hayas descomprimido el Eclipse.
Ahora Eclipse se comportará como cualquier otra herramienta instalada.
4. Instalando el SDK de Android:
El SDK de Android es, básicamente, un gestor que nos ayudará a descargarnos todas las demás herramientas necesarias para desarrollar en esta plataforma: emuladores, documentación, APIs, etc.
El SDK también contiene el AVD Manager que nos ayudará a gestionar nuestros AVDs (Android Virtual Devices) que son los emuladores donde probaremos nuestras aplicaciones.
Podemos descargar el SDK de Android desde: http://developer.android.com/sdk/index.html. Al igual que ocurría con Eclipse el SDK no requiere instalación, simplemente extraemos el archivo comprimido donde queramos, yo lo he situado junto al Eclipse.
5. Instalando ADT:
ADT es el plugin oficial de Android para Eclipse, con él instalado Eclipse sabrá como crear y gestionar proyectos Android; compilar, correr y debugar aplicaciones Android; tendrá acceso a la API de Android para detectar errores de sintaxis y sugerir autocompletados y nos ofrecerá acceso directo al SDK, al AVD Manager y otras opciones más.
Para instalar ADT en Eclipse podemos seguir paso a paso este tutorial oficial de Android: http://developer.android.com/sdk/eclipse-adt.html#installing.
Es probable que en algún momento recibimos un aviso de que no hay plataformas instaladas en el SDK, no hay problema, las vamos a instalar ahora mismo.
5. Configurando el SDK:
Una vez instalado ADT y reiniciado Eclipse accedemos al menú Window > Android SDK Manager. Esperamos a que descargue toda la información y seleccionamos la carpeta Tools y todos sus elementos, y la plataforma más actualizada que haya y todos sus elementos. Hacemos clic en Instalar y dejamos que el SDK se encargue de todo (descargar e instalar), lo cual puede llevar un tiempo ya que son muchos megas.
Y por fin tenemos nuestro Ubuntu listo para desarrollar Android.
Aquí http://developer.android.com/resources/tutorials/hello-world.html un tutorial en el que nos enseñan a crear nuestro primer AVD y nuestra primera aplicación.
Y aquí http://developer.android.com/index.html toda la documentación oficial de Android para desarrolladores (en inglés).
Un saludo!