Ya que esta duda también podría incluir detalles relativos al Pixel Art en sí...

1.¿Que herramientas debo usar?
Paint (para desarrollarlos es un editor más sencillo y cómodo) y Character Maker Pro (para adecentar la paleta en un formato de colores adecuado) para sprites, minis y otros gráficos que pretendas insertar.

Para sprites de exposición (subforo de Gráficas), Paint para diseñarlos y Photoshop para ajustar el número de colores (te permitirá calcularlos con total precisión, procura eliminar el fondo y dejar tildada la casilla "Transparencia").

2.¿Hay alguna plantilla que pueda utilizar para overworlds?
Creo que arriba ya te ofrecieron algunas, para mi gusto parece que tienen los pantalones "cagaos", pero si encuentro alguna plantilla pues te la proporcionaré.

3.¿Como va el tema de las paletas?
Arriba te dieron excelentes indicaciones, así que suponiendo que algún día empleases la rom base de JPAN, como ventaja dispondrías de una nueva paleta que podrás reutilizar con cualquier minisprite, la desventaja es que gastas un poco de espacio (aunque no lo veo exactamente como una desventaja).

4.¿Que tamaño deben tener?
El tamaño dentro del Rom Hacking en sí te lo especificaron arriba, pero si algún día te animas a preparar tu propio sprite (no con la finalidad de insertarlo, sino como mero amor al Pixel Art), el tamaño máximo alcanzado por los sprites ronda los 96x96 píxeles.

5.¿Como inserto los overworlds y los sprites ya sea sustituyendo o creando un nuevo sitio en la ROM?
Hay varios tutoriales muy buenos en los subforos correspondientes, quizás te sirva de ayuda el visitar el tema titulado como "Índice de Tutoriales".

Buena suerte~~