Los mejores tutoriales (yo creo) para empezar, los encontraras en digital-tutors. Son muy buenos pero no todos son gratis
Sobretodo par empezar si no tienes experiencia con otros programas te recomiendo q compres este: Introduction to Maya, 2nd Edition
http://www.digitaltutors.com/
También esta SimplyMaya, estos están bien porque son de descarga directa:
http://www.simplymaya.com/