Es cierto que la mayoría de los programas ofrecen todas las herramientas necesarias para completar cualquier nivel de Pixel-Art, pero como siempre hay herramientas más amigables para ello que ofrecen hacer lo mismo pero con mayor o menor dificultad. Si entras a cualquier foro dedicado a esto todos te dirán que la mejor herramienta en común es el Photoshop CS5. Sin embargo es malo forzarse a usar una herramienta desconocida con tal de intentar trabajar algo aún más desconocido; si no sabes usar Photoshop, te recomiendo que uses cualquiera que sea el programa con el que estés más familiarizado.
Tutoriales hay muchísimos circulando. Yo, personalmente, recomiendo encarecidamente que comiences con sprites simples hechos desde cero antes de ver cualquier tutorial que pueda confundirte. Si se te complica trabajar las paletas de colores, buscas un tutorial sobre el uso de colores. Si tu trazo se vuelve deforme, buscas tutoriales sobre la forma de acomodar los pixeles y el AntiAlias.
Si sabes manejar medianamente el inglés, te dejo el que, a mi parecer, es el mejor tutorial que puedas encontrar, escrito en conjunto por los mejores Pixel-Artist's que puedas ver en Internet:
The Pixel Joint's Pixel Art Tutorial.