You would need to change the .css files to go along with your new colors. What I usually do in this situation if the template offers more then one color choice — say red or black. I’ll chose the one I’m not currently using and edit that. This way if you screw up you can always go back to a default color you can live with.
You could also do a joomlapack backup and put the site in a subdomain or other domain to do your edits and have no worries about screwing up your main site. Then when you’re ready just move the template files over to the live site.
To help find out which .css file contains color codes http://getfirebug.com/ this firefox plugin is extremely helpful when trying ot track down what css file(s) are being accessed.
