1.¿Que herramientas debo usar?
Yo personalmente uso paint para todo, es muy comodo, aunque tambien se pueden con CMP(character Maker Pro), Photoshop... y un montón de herramientas mas, pero la más basica suele ser Paint.
2.¿Hay alguna plantilla que pueda utilizar para overworlds?
Muchísimas! De verdad has buscado en google? Hay muchas, te dejo una de todas formas.
3.¿Como va el tema de las paletas?
Pues hay unas paletas determinadas para los minis y si, son reutilizables, de hecho eso que dices de agregar paletas, solo se puede con la base de JPAN, pero visto que preguntas como sustituir los OW, me indica que te falta experiencia, por lo que no te recomiendo esta base, te recomiendo mucho mas aprender a utilizar las paletas, y para eso estoy yo. Espero que te sirva esta investigacion que hice hace tiempo:
http://wahackforo.com/t-20596/uso-paletas-minis-para-fr-especial-nse
4.¿Que tamaño deben tener?
Un overworld puede tener los siguientes tamaños:
16x16
32x16
32x32
64x16
64x32
64x64
Cualquiera de esos tamaños es compatible, yo tengo de todos los tamaños en mi hack.
Respecto a los sprites, el tamaño es por obligacion 64x64
5.¿Como inserto los overworlds y los sprites ya sea sustituyendo o creando un nuevo sitio en la ROM?
Esto mejor que te busques tutoriales, aunque lo mejor es aprender a base de ir probando. No se si se pueden agregar sprites, pero tienes muchisimos huecos sobre todo porque hay 2 cazabichos, 2 entrenadores guay, 2 entrenadoras guay etc etc... si quitas los dobles tienes muchos huecos nuevos!
Respecto a los minis, primero aprende a sustituirlos, y cuando ya sepas, si usas FR (si usas ruby lo siento pero ya está al maximo) puedes agregar minis usando este tutorial:
http://wahackforo.com/t-23315/fr-graficos-agregar-nuevos-minis