Palettes are stored in PALETTE.BIN.  The format is easy to pick out; 256 colors * 3 bytes per color.  There are ten palettes (nine if you exclude palette 04--a blank palette), and some padding zeros at the end.

Colors themselves are (for some reason) scaled by 4 upon loading.  I don't know why they were scaled DOWN to begin with, seeing as the bits are there, but whatever.  Map background colors do NOT appear to suffer from this.


The structure of a fully assembled palette is as follows:
Color 0 = transparent (is black)
Color 1 = black (hard)
7 color runs of 16 colors each (going from dark to light).  These colors are affected by brightness
7 color runs of 16 colors each.  They are exact duplicates of the above, except THEY are NOT affected by lighting (which is why explosions always look the same).
30 colors used by the map background.


The first palette appears to be the game palette.  The second a menu palette.
The remaining palettes appear tied to backgrounds, and they are merged with the game palette on map loading.



Ambience affects loading.  The formula is ridiculously complex, and therefore I altered it.  unfortunately I lost my alteration, but it was something along the lines of (color) * (((ambience + 32) / 32) ^ (sqrt(3)))