The tutorials that ship with Maya in the online docs, and the Learning Maya book is also a good starter..
Personally I find the Learning Maya book a bit too hard for a complete beginner, but it covers some nice topics..

Then I would take a look at the tutorials here at SM, both written tutorials, and the free Videos.. And then I would buy some of the videos from here, when I needed to go deeper into stuff.

As someone else said, use Google to search for Maya tutorials, and alsoe try looking at other 3D tutorials, lots of the stuff is the same principles between 3D applications.

Good luck