Once the system had been released, games could be made in "dual-mode" which would support a monochrome palette when played on the original hardware, but would use custom colorization on the GBC[2].
I'm trying to find more technical sources but haven't located any yet, so if anyone help me find more information I'd be very interested.
EDIT: I found a little more information. Here's[3] someone who disassembled the GBC boot ROM. It looks like on boot, the system would check to see if the inserted cartridge is one of 93 first-party games, and apply a specified palette; otherwise, it would just apply a default palette.
[1]: http://www.neogaf.com/forum/showthread.php?t=497582
[2]: http://www.allgame.com/platform.php?id=17662
[3]: http://www.vintage-computer.com/vcforum/showthread.php?19247...
http://chrisantonellis.com/files/gameboy/gb-programming-manu...
Interesting article, though. It would be interesting to see more games designed this way, though I doubt that'll ever happen. Pity, that.