This post isn’t so much about how to get started, but about how easy it is to get started with Android development. In about 5 min (excluding download time), I had a working Android app that spit out Hello Android. Here is how you can get started, should you so choose.
Download and install Eclipse (I installed Classic)
Download the Android SDK and read the quickstart (Install ADT plugin for Eclipse mainly)
Run through the Hello Android tutorial
The download is painfully slow, but after you get it installed, creating new apps is a breeze. I was actually really surprised and enthused to play around with the Android SDK. The developer wiki is top notch and the integration with Eclipse made getting started simple. I haven’t done anything too complex yet, but getting started is the hard part.
Check out the Next Steps if you are looking for more tutorials and tips.