This is a fairly simple process really, but since it does require some knowlege of the MPQ and making mpq files I'll write it out step-by-step anyway.

Step #1- Getting the files needed
 Go into StarDraft, open up a cwad or make a new cwad, it doesn't matter. Import the following files from the StarDat.mpq file into your cwad:
 - game\tunit.pcx
 - game\tminimap.pcx
Then extract them from the cwad onto a directory on your Hard Drive, but remember that they are in the mpq directory called "game\".

Step #2- Editing the files
 To edit the pcx files all you really need is MS Paint (the program that comes with windows), but any paint program will work just fine, I used Paint Shop Pro. First open up "tunit.pcx" this is just a tiny graphic (only one pixel tall), and it has all of the team colors in a row (plus some other unused team colors), zoom in to the max on this file so you can see everything very clearly.
 Find the color that you want to edit (I used teal and brown for my little example). Then you have to be careful so you only use colors from the SC Unit pallete, any other colors will crash it, or mess up really bad.
 When you've edited tunit.pcx to your liking, save it, and open up tminimap.pcx. This is the file that StarCraft references to when placing the team color on the minimap view (afterall, you don't want a black team color displaying a teal color on the minimap). FInd the color that coinscides with the team color that you just edited in tunit.pcx, then change that color to what it now is in tunit.pcx. Then save and close.

Step #3- Implementing your new team colors
 Unlike most custom changes, you can't use StarDraft to make these changes work. Believe me, I tried it, it just crashes when you try and run it.
 Instead, you have to make a custom mpq and place the files in there. If you don't know how to do this, you'll need to learn how. We have a tutorial that gives you the basics, it should be in the StarDraft Resource section.

Step #4- Run it!
 IF you've completed all of the steps and now have your custom MPQ ready, all you have to do is run it, I recommend just running Staredit and testing it there. If all went right, you should be able to go to the color that you replaced, and try placing one of it's units, then they should come up in the new colors. This will also work in StarCraft as well, so have fun with it.