I have read that the adhesive used by regular labels (like for envelopes and manila folders) can eat through the thin plastic tops of cheaper CD's and damaged the shiny layer over time, similar to the damage of using regular permanent markers.

A label can also unbalance the CD when it spins. I've heard CD's with labels that didn't "sound right" spinning in the drive, although I did get the data off just fine.

In addition to ironraven's suggestion, I have a set of Imation alcohol pens made for writing on CD's. It comes in a set of red, blue, and green pens. I think it was from CompUSA and cheap.