This is a pretty simple process, and it can add some great enhancements to the visual appeal of your towns/cities and your Pokemon sprites as well.

NOTE: This tutorial only applies to SGB users. If you're playing under GB or GBC settings, these suggestions and changes won't apply to you, and there's really no point going any further...

Find the Palette Constants and Their Corresponding RGB Values

To find the palette constants, you'll look in constants\palette_constants.asm. The beginning of the file is dedicated to defining the functions that set the palettes, but the constants for the palettes themselves are located immediately below this.

Now that you have eyes on the constants, go to data\sgb\sgb_palettes.asm. Here you'll find the RGB values associated with each SGB palette in the game, with each list entry corresponding to its location on the constants list.

How the Numbers Work

You'll find that everything is broken down into 4 sets of 3 numbers. Each palette is composed of exactly 4 colors, and each color has its own RGB combination. Generally, combinations of higher numbers yield lighter colors, while lower numbers produce darker colors.

Each palette has 2 colors in common: 31,29,31 (the first one, nearly pure white) and 03,02,02 (the last one, nearly pure black). To maintain some level of consistency between palettes, I personally wouldn't mess with these values, unless you change ALL of them. Additionally, each city/town shares the third value, 20,26,31, which gives the light-blueish highlights that ride alongside the primary color of that city/town. It also dictates the color of the water, so I really wouldn't touch this unless you plan to make it a different blue.

Editing Palettes

If you're looking to edit a city/town palette, the second set of three RGB values is what I would fiddle with. Of course, you're free to change whatever you want. One example of a change I implemented was to make Viridian City a much greener... green:

...
	RGB 31,29,31, 20,25,25, 20,26,31, 03,02,02 ; PAL_PALLET
-	RGB 31,29,31, 17,26,03, 20,26,31, 03,02,02 ; PAL_VIRIDIAN
+	RGB 31,29,31, 05,24,15, 20,26,31, 03,02,02 ; PAL_VIRIDIAN
	RGB 31,29,31, 20,22,24, 20,26,31, 03,02,02 ; PAL_PEWTER
...

The resulting change looks like this (original on left, updated on right):

While city/town palettes really only have one color that can easily be changed, Pokemon palettes have two. In addition to the universal black and white, every Pokemon palette (besides PAL_MEWMON) has two shades of similar color, with the RGB values of the lighter color listed first.

Speaking of PAL_MEWMON, change its RGB values AT YOUR OWN RISK... trainer sprites use that palette, so you'll end up messing with their color scheme if you do.

Because of the "two shades of similar color" thing, we can't get terribly creative with our palettes. Trying to put two significantly different colors on the same sprite will turn it into a mess. To fix this would require a massive effort retouching the light-color and dark-color regions of each sprite... a separate process from adjusting palettes, and one that goes beyond the scope of this tutorial.

Still, I can share one of my own adjustments. I changed PAL_PURPLEMON as follows:

...
	RGB 31,29,31, 21,25,29, 14,19,25, 03,02,02 ; PAL_CYANMON
-	RGB 31,29,31, 27,22,24, 21,15,23, 03,02,02 ; PAL_PURPLEMON
+	RGB 31,29,31, 23,18,20, 18,12,20, 03,02,02 ; PAL_PURPLEMON
	RGB 31,29,31, 28,20,15, 21,14,09, 03,02,02 ; PAL_BROWNMON
...

This makes it slightly darker, as seen in Muk's sprite:

That's that for adjustments. Have fun messing with colors!

NOTE: if you adjust PAL_GRAYMON, you'll end up messing with the palette for CEMETERY maps (i.e. Pokemon Tower and Agatha's Room). See the following section for how to prevent this.

Adding a New Palette

This is as simple as adding to the list in constants\palette_constants.asm, then defining its RGB values in the corresponding slot in data\sgb\sgb_palettes.asm. I'll show how I added a new palette I called PAL_GOLDMON.

First, in constants\palette_constants.asm:

...
	const PAL_GRAYMON   ; $19
+	const PAL_GOLDMON   ; $19 <-- I typically will go through and adjust the commented constant values
	const PAL_SLOTS1    ; $1A
...

Since I put the new constant after PAL_GRAYMON, I'll do the same for the RGB values in data\sgb\sgb_palettes.asm:

...
	RGB 31,29,31, 20,22,24, 14,16,18, 03,02,02 ; PAL_GRAYMON
+	RGB 31,29,31, 31,26,00, 26,21,00, 03,02,02 ; PAL_GOLDMON
	RGB 31,29,31, 26,21,22, 27,20,06, 03,02,02 ; PAL_SLOTS1
...

Now assign the palette to a Pokemon in data\pokemon\palettes.asm. Let's give it to one of the starters... how about Charmander?

...
	db PAL_GREENMON  ; VENUSAUR
-	db PAL_REDMON    ; CHARMANDER
+	db PAL_GOLDMON   ; CHARMANDER
	db PAL_REDMON    ; CHARMELEON
...

And here's what it looks like when picking your starter in Oak's Lab:

If you want to adjust PAL_GRAYMON without changing the CEMETERY maps, just add in a new constant called something like PAL_TOWER and assign the vanilla PAL_GRAYMON RGB values to it. Follow these instructions:

Open constants\palette_constants.asm and insert your new constant (I put mine after the PAL_CAVE constant, near the end):

...
	const PAL_CAVE       ; $26
+	const PAL_TOWER      ; $27
	const PAL_GAMEFREAK  ; $28
...

Open data\sgb\sgb_palettes.asm:

...
	RGB 31,29,31, 21,14,09, 18,24,22, 03,02,02 ; PAL_CAVE
	RGB 31,29,31, 26,21,22, 15,15,18, 03,02,02 ; PAL_TOWER, using the vanilla PAL_GRAYMON values
	RGB 31,29,31, 31,28,14, 24,20,10, 03,02,02 ; PAL_GAMEFREAK
...

Finally, open engine\gfx\palettes.asm, find the SetPal_Overworld: routine, and scroll down to .PokemonTowerOrAgatha:

...
.PokemonTowerOrAgatha
-	ld a, PAL_GRAYMON - 1
+	ld a, PAL_TOWER - 1
	jr .town
...

Now your CEMETERY maps will remain the same color while you adjust your Pokemon palettes.

One final note: if you create a new overworld city/town map, you'll want to define a color palette for it, then list it in constants\palette_constants.asm and data\sgb\sgb_palettes.asm in the same slot (relative to the other cities/towns) as where you put it in constants\map_constants.asm.

Quick example: in my ROMhack I made a post-game area called the "Park of Fame," which has a bright golden-yellow hue to it.

In constants\map_constants.asm I have:

...
	map_const CINNABAR_ISLAND,               10,  9 ; $09
	map_const INDIGO_PLATEAU,                10,  7 ; $0A
+	map_const PARK_OF_FAME,                  15, 12 ; $0B
...

It's after Indigo Plateau there, so I need to be consistent in constants\palette_constants.asm:

...
	const PAL_CINNABAR   ; $0A
	const PAL_INDIGO     ; $0B
+	const PAL_PARKOFFAME ; $0C, don't worry about the commented constants being one off from the above list...
...

Finally, make sure it's in the same list slot in data\sgb\sgb_palettes.asm:

...
	RGB 31,29,31, 30,10,10, 20,26,31, 03,02,02 ; PAL_CINNABAR
	RGB 31,29,31, 22,14,24, 20,26,31, 03,02,02 ; PAL_INDIGO
+	RGB 31,29,31, 31,31,07, 20,26,31, 03,02,02 ; PAL_PARKOFFAME
...

And finally, here's what its palette looks like in the game:

I think that covers everything. Happy editing!