editing the palette, is easy enough. just use a hex editor to edit the colours you want. ive changed a lot of the geoscape colours for my tc.
however... you also need to change the darkened version's to something similar as yrizoud has mentioned. its easy enough just can a pain with tons of numbers everywhere.
I got the palettes off the xcom wiki, shrank them to 1/3 so 1 pixel is 1 colour then you have a index for the hex editor. every colour is 3 entrys ie. 11 22 01 is one colour so you need to times your index number by 3 to find the exact colour in the palette.dat. ie 1x3 is 3 and that's the second colour in the palette, first colour starts with 00, second 03 third 06 and so on
Hope that makes sense and helps