CSS is the easy way of doing it, if your site consists purely of solid colours in areas. Otherwise if you're using images, you could do some JavaScript to do it, or if your using a server-side language it would be easy as well.
One way in which i deploy is.
Colour Scheme is saved as a simple cookie string.
When the site loads, the cookie is retrieved and loads the images from the particular folder based on the colour scheme, for example
ColourScheme\background.gif
Where ColourScheme is what the cookie value would be.
So if there exists a cookie value "Red"
Red\background.gif.
So for every colour scheme, you just have a folder called Red with the images located inside the folder.
Simple.