With version 3 of the Google Maps API, the easiest way to do this may be by grabbing a custom icon set, like the one that Benjamin Keen has created here:
http://www.benjaminkeen.com/?p=105
If you put all of those icons at the same place as your map page, you can colorize a Marker simply by using the appropriate icon option when creating it:
var beachMarker = new google.maps.Marker({
position: myLatLng,
map: map,
icon: 'brown_markerA.png'
});
This is super-easy, and is the approach I'm using for the project I'm working on currently.