Para empezar:
El mejor programa para hacerlos: Simple y llanamente Microsoft Paint. Es simple, rápido y barato.
Condiciones de trabajo:
Cuando haces un sprite, lo mejor es ajustar tu pantalla al mayor tamaño posible. Una resolución de 800x600 es la más adecuada. De la misma manera, al trabajar en Paint, ajusta el zoom a 8x. Por último, aumenta el brillo de tu monitor SÓLO si vas a trabajar con distintos tonos de negro.
Empezando:
Reconozcamos primero lo que vamos a usar. Primero, el campo de trabajo.

Ajusten el tamaño del campo a 64 x 64 píxeles. Pueden hacerlo manualmente (viendo abajo en la barra de Ayuda, donde normalmente aparecen las coordenadas del mouse), o pueden irse a la segura, presionan CTRL+U y ajustan las dimensiones a 64 x 64.
Segundo: las herramientas. No vamos a usar toooooodas las opciones de Paint. Enumeradas están (ver dibujo de arriba):
1.- Selección libre (no se usa)
2.- Selección rectangular.
3.- Borrador.
4.- Cubo de pintura.
5.- Extractor.
6.- Zoom.
7.- Lápiz.
8.- Brocha/pincel (opcional).
9.- Spray (no se usa).
10.- Texto (no se usa)
11.- Línea recta(opcional).
12.- Línea curva(opcional).
13.- Rectángulo (opcional).
14.- Polígono (opcional).
15.- Elipse (opcional).
16.- Rectángulo redondeado (opcional).
La paleta de colores:
Como notarán en los sprites de Pokémon, se utilizan varios tonos distintos de color, para dar el efecto de luz y sombra, el cual sirve para darle relieve a la imagen. Para que el sprite tenga verdadero aspecto de sprite de GBA, hay que usar las variaciones de tono, por lo que la paleta tal como está no sirve más que para crear abominaciones de baja calidad. Den doble clic en la paleta de abajo, o seleccionen Colores->Modificar colores en las opciones de arriba para accesar al menú de Personalizar color.

Ahora a la acción:

Para aprender a hacer un sprite hecho completamente por nosotros, sin usar partes de otros sprites, se va de a poco:
Primero, "dibuja" con el lápiz la forma de la cabeza (fig. 1). Pueden si quieren usar una herramienta "Línea" (recta o curva) o una "figura" (rectángulo, elipse, polígono o rectángulo redondeado), pero lo más aconsejable es usar el lápiz. Una vez dada la forma de la cabeza, se sigue con el cuerpo (fig. 2 y 3), siempre yendo de a poco. Una vez terminado el cuerpo, se hacen los detalles, comenzando por las partes simples (fig. 4) y siguiendo por las que son "adorno" (fig. 5). El siguiente paso es colorear por dentro (fig. 6). Para esto, eligen un tono del color que desean usar, y pintan usando el cubo de pintura. En este paso es opcional el pincel como substituto, pero es más práctico el cubo. Una cosa importante: No dejen el blanco tal como está; busquen un tono ligeramente más oscuro. Una vez hecho esto, busquen tonos medianamente oscuros de cada color, y úsenlos para reemplazar el negro el las líneas exteriores (fig. 7).
Lo siguiente puede ser la parte complicada: dar los efectos de luz y sombra (fig. 8). Aquí tienen que elegir un punto de foco del cual la luz proviene, preferentemente la esquina superior izquierda. Con eso en mente, elijan un tono claro de cada color y vaya agregando el color a la imagen al tiempo que le dan forma, luego hacen lo mismo con un tono oscuro pero por el lado opuesto a la luz, y dando prioridad de espacio al color central. Una vez hecho eso (lo cual requerirá algo de práctica), le dan el toque final, que es darle efectos de luz y sombra a las líneas de dibujo (fig. 9). Para la demostración, el efecto de luz lo di con el mismo tono oscuro dl color correspondiente, mientras que el efecto de sombra lo hice con un tono ligeramente másclaro de negro. Recomiendo no usar negro puro de la misma manera en que recomiendo evitar blanco o cualquier otro color de la paleta básica. Muchas veces esos colores se usan como fondo de gráficos transparentes.
El resultado final es el que verán a continuación, ocupé sólo 13 de los 15 colores que ocupa un sprite de GBA (sin contar el color de fondo). Pueden usar más colores, pero siempre es mejor darle un toque de "realismo".

Recuerden, esto es sólo una guía, no tienen porqué seguirla al pie de la letra, una vez que se acostumbren a hacerla lo harán a su manera.
espero que esto sirva de algo, y gracias por tomarse la molestia de leer esto ^^