Gba, soporta como máximo 256 (tomando como "mínima unidad" el color 0, si no, 255).
Soporta la misma cantidad tanto para backgrounds, como para sprite palette. Fíjate usando el emulador en el Palette viewer.
Ah, y los colores son de 15 bits, es decir, van de 8 en 8, por así decirlo.