Mira, Principalmente Paint, y pues como ya han dicho, buena imaginacion, para comenzar no esta de mal conseguirse unas bases-plantillas, lo mas original posible, y saber que colores utilizar y todo eso, asi a la gente le encantaran tus sprites 7u7
Con GIMP, Photoshop, o Paint si no hay más remedio. Pero viendo que desconocías esto, te animo a echarle un vistazo a tutoriales sobre spriting, puesto que tiene una técnica más complicada de lo que parece.