The GBC hardware is pretty similar to the original Game Boy hardware. Besides the color graphics, it has the option to run at 8 MHz instead of 4, which doesn't really amount to much except less slowdown when many sprites are on-screen, and has twice the amount of VRAM, which obviously allows for better animated/more sprites and more detailed backgrounds. (Game Boy Color games that are backwards-compatible with the original Game Boy can only use half of the available VRAM, though. It's why the Korean versions of Pokemon Gold and Silver can only be run on the GBC - the graphics used for the hangul poke into the second VRAM bank.) Other than that, the systems are extremely close, if not identical.
If I'm remembering right, adding color to a Game Boy game can be done by adding in palette data, adding in code to load the palette data (since why would the original Game Boy ever need that?), and then assigning palette attributes to individual tiles. There's a program called the Game Boy Colorizer that can automate the process to an extent, but it's very limited, and not very good besides that.
Maybe someone else can explain it better than I can, since I've never done it before, but there you go.