Все зависит от того, что вы уже знаете.
Если вы ничего не знаете о программировании вообще, то вам сначала бы научиться программировать) Можно сразу на языке Java учиться.
Если вы уже знакомы с программированием, с Java, ООП и прочим и хотите попробовать себя в андроиде, то я посоветую вам учиться по урокам из http://startandroid.ru/
Сам учился по этим урокам... После первых десятков уроков я уловил суть и дальше заходил по мере необходимости и искал только то, что надо...
Какие-то книги я бы не стал советовать. Книгу обычно только читают и не практикуют. А без практики, как и везде, в программировании нельзя.