First of all you need a good paint program that can handle PSD files.
PSD is Photoshop's native format so it's best to use this program.
Other paint programs may work or not... I don't know for sure, you can try using your paint program but always keep a backup of all files you modify or you may need to reinstall Gamespy when something goes wrong.

I've used Paint Shop Pro 7 (you can get a demo with full functionality at www.jasc.com ) but this description should apply to all paint programs.
*Paint Shop Pro 7 works perfectly (and Paint Shop Pro 4 does not work at all)

From within your paint program load the file "peer_chat_border.psd" which usually resides within "GamespyArcade\Skins\(default)\".
You'll see a box and at the bottom a colorful line. Pick your paint program's zoom tool and zoom the start of that line so you can see the colors more clearly.

There are 16 colors - for your convenience I've listed each color field with its horizontal (X) position, its color and a description of functionality:

Now select the paint brush and turn its size down to the minimum value so it can paint single pixels.

Then paint whatever you like into these fields and save the result overwriting the file you just opened (you kept a backup, didn't you?) and restart GSA.

Notes:

I personally recommend to put the color of registered and "away" users (maybe also the color of VIPs and admins) to the color of normal users 'cuz all the colors all the time are too annoying.

The link color can be set within the Gamespy chat configuration - that's why it's not listed here.