Programming for Android is done in Java. If you're never done Java, I wouldn't recommend you start with Android just yet.
If I were you, I'd learn Java first, and then move on to Android. All you need is a basic understanding of the language though, for which you can find millions of tutorials on the web (Sun tutorials, etc). I also think getting an actual book is always worth it. It'll save you lots of time searching for stuff on the Internet. You can get used Java books for a buck on half.com.
Once that is done, then moving to Android should be much easier. For one, you'll know what is part of Java and what is part of the Android framework, and if later you need to do something in pure Java, you won't be looking for Android framework classes or idioms.
For Android, the first step would be to do the Hello World tutorial, and then the Notepad tutorial.
After that, lots of code snippets can be found under Sample code.
I also highly recommend this website, which provides lots of tutorials.