To me it looks like colored coins just have additional information stored. It sounds like a struct that has an additional variable. There's probably more to it, I did not yet check that in the source code, but it sounds easy to implement (just add the variable).
It is not hard to implement colored coins. There are a few details you need to keep in mind, though:
Remember for each UTXO which color it was for
Make sure to verify that when a transaction generates colored coins, they are either the same color as at least one of the inputs (and their sum matches) or a completely new color (for example, derived from the transaction ID).