Google have launched Android Training. This will give Android beginners a step by step approach to getting started with Android.
It is a problem driven approach so each class will look at a problem and show how it should be approached. There are plenty of sample apps to get you started.
I would recommend that you place close attention to the following classes:
This class will show you how to avoid common mistakes when trying to cater for the various Android screen sizes and also how to adapt your UI for various screen flows. If you design your app with multiple screen sizes in mind from the start it will save you a lot of pain later.
This is a great lesson that teaches you how to save battery power by disabling background tasks when the state of the device changes. Such as loss of connectivity.
As well as Android Training, there are lots of other articles and tutorials. This should get you well on the way to developing your first Android App.
However, if you a looking for more Android tutorial resources, it is worth checking out Mobiletuts+ tutorials for Android. They have lots of *really* good tutorials from beginner to advanced. They also have some specialised premium tutorials that take you to the next level but there are lots of free ones to get you started.
Here is a sample of some of my favourite tutorials from Mobiletuts+:
This tutorial gives you step by step of how to get your finished app published in the Android Market from checking what permissions you require to deciding on the SDK compatibility.
This is the first of a series of tutorials on Android Fundamentals. I would recommend working though all of the tutorials in this series. This tutorial will show you how Android uses content providers to enable applications to share and use data.
This tutorial is part of another great series from Mobiletuts+ on Android UI Design. Fragments were introduced to allow you to break your UI into separate independent parts. On a larger screen such as a tablet multiple fragments can be show at ones. Fragments were introduced as part of 3.0 but you can add it to 1.6+ apps. This tutorial will show you what you need to get started.