O que é preciso pra começar a programar para Android

Se você já tem familiaridade com a linguagem java você já deve saber como baixar, ou ter em seu computador instalado, o Eclipse IDE e o JDK(kit de desenvolvimento java), então só vai precisar fazer um update no Eclipse.
Vamos começar pelo ADT (Android Development Tools), a versão do Eclipse que estou usando é a Indigo, você vai em Help>Install new software...

Na janela que se abre coloque este endereço https://dl-ssl.google.com/android/eclipse/ e clique no botão Add. Se abrira uma janelinha preencha o campo nome com Android e clique em Ok.

Na próxima janela que se abrirá como a da figura abaixo selecione tudo e clique em next, ele irá baixar os arquivos aparecerá mais uma janela você clica em continuar de novo, mais uma perguntando se você aceita os termos do software, depois disso começará a instalação do software e quando a instalação terminar o Eclipse irá pedir para reiniciar.

Depois que o eclipse reiniciar aparecerá um novo botão nele igual ao da imagem abaixo, o android sdk manager, clicando nele você poderá baixar as API's necessárias, exemplos e extras.
Para saber qual a versão mais utilizada do Android acesse este site, ele é constantemente atualizado com base nos aplicativos baixados no Android Market, lá também as resoluções de telas mais usadas, emfim é uma boa fonte para saber como atingir o maior publico possível .

Selecione a versões para as quais você deseja programar para serem baixadas e instaladas você também pode baixar os exemplos e estamos prontos para pôr a mão na massa.
Se você não têm o Eclipse instalado no seu computador pode baixar ele completo já com o ADT instalado no site developer android, nesse caso não precisará fazer o processo acima para instalar o plugin.