Bueno, creo que debes de empezar por aquí. Pero te diría que sin experiencia, hacer pixel art para 16 bits puede ser una entrada en arte muy muy brusca.
No obstante todo lo que necesitas está en Pixel Prospector:
http://www.pixelprospector.com/the-big-list-of-pixel-art-tutorials/
En cuanto a herramientas, puedes empezar por Graphics Gale. Pero cualquier búsqueda en google sobre cual es la mejor herramienta para pixel art, te saldrán un buen montón de opciones, algunas especiales para escenarios, eso sí, no todas son gratuitas.
¡Suerte!