It's pretty easy.  You only need to search at integer 1 bytes for the colors, and with the size of the memory, it shouldn't take long to find out if you've found them or not.

FCEU/FCEUX has a PPU viewer that lets you see the values of the colors (not sure if using the emulator to mod colors is a good idea though, since last time I tried, changing black affected more then just the black background color.).  The value for the black background color is ususally 0F (10, in decimal), but you could also use PPU viewer to assist with finding a background color you know that changes. 

With NES, the black background color is usually grouped with the stage colors.  So if you find one of the stage colors, check around it to find the black background color. You could also try searching with the address range set to All but there's a possibility of what you find won't work the next time you load up the emulator (savestates may remedy this).

Refer to this for the colors the NES uses.

Here's a method I've used.  It requires GBA Color Picker for it (unless you wanna try the alternate method further down):

1. Take a screenshot.

2. Open the screenshot up in an image editor that shows you the RGB values to a color (like GIMP), and pick a color to get values from.  Make sure none of them are above 248.

3. Enter the RGB values into GBA Color Picker, and do a search at integer 2 bytes for the value it gives you.  Not a guaranteed way to do it, but I've had a bit of success with it.

If you want to use Emulator for the address range, it can be dicey.  Some color addresses are outside the address range Artmoney lets you search in.  If you can't find anything, try using all All for the address range (though you risk what you find not working next time).  For SNES and Genesis emulators, it may be possible to find addresses that affect the black background color to multiple games.

Edit: Turns out there's more programs then GBACP for converting the color values.  All I had to do is search for a 15-bit color converter. :p

Here's a couple methods to try that might work:

1. The GBA Color Picker method mentioned above.  If you're unable to find a value, add 8000 (hexadecimal) to the value (7C1F becomes FC1F, for example) and try that.

2. Search for HTML colors at integer 3 bytes.

3. Try searching for values with reversed bytes (3412 or 563412 instead of 1234 or 123456).

8000 (32768, in decimal) is sometimes used as the value for black instead of 0000.  0000 tends to be used as the transparency color, and can sometimes be used by you to hide a character/background element.  For the HTML colors, they're actually integer 4 bytes.  The part I exclude by searching at ingeter 3 bytes may control the Alpha channel (it did for a couple PS2 games I found html colors in).

I don't know if #2 or #3 work for NDS games.

I recently tried to come up with an alternate method in the event I'm no longer able to use GBACP (or for those who currently can't use it because of .dll issues).  If someone can improve this method, please do.

First, some notes on the workings of GBACP (you don't really need to know any of this)

First, take a screenshot of the game and open it an image editor (like GIMP). 

Next, pick a color in the screenshot and jot down the RGB values to it.  If you see that the values to any of the colors aren't a *multiple of 8, they should be rounded down to the nearest one. 

After you do that, get a calculator, and:

For Red: Take the value and divide it by 8

For Green: Take the value and multiply it by 4

For Blue: Take the value and multiply it by 128

Add the numbers you get together, then convert the total into hexadecimal.  Or you could just uncheck the hexadecimal view and edit boxes, search for the decimal value at integer 2 bytes in Artmoney. :p

If you can't find a color mod, try adding 32768 (8000 in hexadecimal) to the value.

Here's an example for #7BFF7A (R=123 G=255 B=122)

Round R down to 120, B to 248, G to 120

120÷8 =15
248×4=992
120×128=15360

15+992+15360=16367 (3FEF, in hexadecimal)
 
*for quick reference, they are: 8,16,24,32,40,48,56,64,72,80,88,96,104,112,120,128,136,144,152,160,168,176,184,192,200,208,216,224,232,240,248

Also, I've only encountered this for Angel Eyes, The Rumble Fish and KoF Neowave so far, but I'll mention it just in case: Try swapping the steps for red and blue.

I don't know how to find exact values, but I have been able a method to find color mods.

What I mean by "RGBW":

The color values are integer 2 bytes.  Each nibble affects a color channel.
Example color value: 1234

2 controls the red channel
3 controls the green channel
4 controls the blue chanel
1 controls the brightness to all 3 (white)

So, now that that explanation's out of the way, here's the method I came up with:

-Go to the Test Menu, and select color test.

- Here's the color values the color bar test should have:

Red
F100 F200 F300 F400 F500 F600 F700 F800 F900 FA00 FB00 FC00 FD00 FE00 FF00

Green
F010 F020 F020 F030 F040 F050 F060 F070 F080 F090 F0A0 F0B0 F0C0 F0D0 F0E0 F0F0

Blue
F001 F002 F003 F004 F005 F006 F007 F008 F009 F00A F00B F00C F00B F00D F00E F00F

White
F111 F222 F333 F444 F555 F666 F777 F888 F999 FAAA FBBB FCCC FDDD FEEE FFFF


- Try searching for F00D or F00F.  You'll find an address that usually mods that color on the fly, but if you don't, go the the main menu, change the value, and see if it got modded.

- Once you find it, set the address range around the color mod you found, and go poking the addresses to try and find what you want to color mod.

- Black might be F000.  Magenta is FF0F.

- Values I tend to use to see if I found a color mod: 7C1F (magenta), FFFF (white).

- I don't know if this applies to all NES games, but if you find all the color addresses to a stage, they will affect almost all the other stages in the game.

- If I'm looking for the black background color, I try searching for a background color, then I do a custom address range search around it.  It's not as reliable as I'd like it to be, and I end up eventually just stumbling onto it looking for something else (isn't that the way, sometimes?). :p

- Sometimes you won't see if you've affected a color unless you cause the screen to change somehow (like going to the map screen in Legend of Zelda: A Link to the Past, for example)

- Sometimes a color won't stay at the value you set it to.  This can be a problem if the the game constantly resets the value on you, because it means you may have to try and convert what you found so you can use the emulator's cheat utility and try to affect it more directly (again, maybe I should do a tutorial on that?). 

- For some games, the black background color won't always be black.  In KoF XI, it's not black in the Cambodia stage.  In Capcom Vs SNK 2, it fades to white during that fade to white before the title screen.

- If you're able to find a color mod for a stage boss, it'll probably affect some of the enemies earlier in the stage too.  That's because only the enemies currently on screen are assigned a set of color addresses.

- I was also able to color mod a couple games for MAME and Kawaks by searching for HTML colors at integer 3 bytes.  This is tricky, though.  Sometimes you'll be able to find color addresses in MAME's debugger via memory dumps.  Other times, there's a good chance the color mod you found isn't in the memory at all (one of the things with searching through all the memory addresses in Artmoney is you can also affect the emulator.  I once accessed the layer enable/disable options to DeSmuMe, using Artmoney because it was efficient).

- An obvious way to find a P1/P2 characters colors: multiple savestates of the character going through different color changes.  Sometimes, savestates of multiple characters; though there's a chance all the player characters are assigned their own groups of color addresses.

- I recall the GBA Color picker method being kinda usable for Sega Master System.  ......At least it was when I tried to hack Sonic on SMS for KGens.  It was outside of the address range though.

- This probably won't help too much, but one way you can try to narrow down your search faster is to search for a group of colors via searching for a sequence of values.  Colors are usually arranged from brightest to darkest, like this for example: ██████████
That's the colors to Ryu's gloves in Street Fighter 3: Third Strike (in that order.......also, he has 64 colors you can mod, transparency included).

- In Castlevania: SoTN, the colors won't change until you reload the stage you want to mod the colors to (this means going through the CD room to the next area, then going back through the CD room), despite being able to color mod Alucard on the fly.  Mentioning it in case there are other games that do this.

- Be careful when color modding outside of the emulator address range, because the colors won't change back when you reload your savestate.  You have to either change them back manually, or shut down the emulator and load the game back up.