You can access the Palette Editor from the Map Editor, by selecting "Switch to Palette Editor" under "Palette" in the menu. To start creating a new color palette, select "modern" from the list, then change the name (for example to "mynicepalette") and hit Save.
There are over 200 colors, but you don't need to change all of them to give the game a new look and feel. The colors are roughly grouped up in a couple of sections. First up are eight groups of nine colors for the nine player colors in the game (including neutral). These are followed by some skintones and then the colors used for in-game effects as well as the colors of trees, grass, mountains and so on. The colors that start with "logo" are used for the logo and icons on the main menu. After that are colors for the in-game Phases Graphic that shows which phase the game is in, followed by various colors used by the rest of the UI. Finally at the end there are some partially transparent colors used for shadows and lighting effects.
You can edit colors by clicking on their colored square, and when you edit the colors used in-game, the changes are immediately applied on the map in the background. You can also go back to the Main Menu with the Palette Editor open to see the effect of your changes on other screens, although some colors are only reloaded when restarting the game.
Don't forget to save when you're happy with your creation!