A ver si te aclaro algunas dudas
Una paleta no es mas que un array (o vector) donde se guardan los colores, es decir, un mapa de colores. Viene a ser lo mismo que una paleta de un pintor, donde tiene sus colores para pintar en el cuadro.
Y un Sprite no es mas que otro array, que identifica por cada pixel que color de la paleta utiliza.
Ejemplo:
Supongamos que tenemos una paleta así:
paleta = {ROJO, VERDE, AZUL, BLANCO}
y un Sprite:
sprite = {0, 0, 0, 3, 3, 3}
Es decir, tenemos una paleta con 4 colores, y un sprite que es una linea (por ejemplo) con 3 pixeles rojos y otros 3 blancos. Un sprite no tiene información de color, sino que "colores" usa de la paleta. Ahora si tu coges y cambias el color de la paleta blanco (el 3) y lo pones por uno marron, nuestro sprite ahora sera blanco y marron sin tener que tocarlo....
Esto se utiliza mucho para los juegos. Por ejemplo, el Splinter Cell de móviles, tiene sus sprites base (Sam Fisher con todos sus movimientos) con su paleta básica (su traje normal), y luego además tiene varias paletas que cambia según el entorno, por ejemplo cuando se mete en la oscuridad cambia por una paleta que son tonos muy oscuros, luego tiene otra con agua en partes del cuerpo, otro en el sol ....
De esta manera ahorras muchisimo espacio, ya que tienes tus Sprites (que es lo que ocupa), y varias paletas que usas según te venga bien, ya que cada paleta ocupa muy poco (el Splinter Cell en cuestión son 14 colores por paleta).
Bueno, espero haberte ayudado y que no te haya abrumado mi rollo xD. Si hay alguna duda más preguntad