Definitely not a hard pen/pencil! Apparently, the layer you are writing on is not only thin, but brittle and is about the only thing between you and the surface/film that carries the data. I've always used felt marker pens, usually that stated they were made for writing on CD's. I may be being ripped off, but many CD manufacturers seem to be OK with those things. For our church I've bought ink-jet printable Taiyo Yuden in stacks of 100 for $33. Unprintable ones are a little cheaper and I suspect that no-brand CDs will be even more susceptible to data loss by whatever method of marking you use. But the harder the pen, the more likely the damage of the recording layer.
Oh, I've used Fellowes labels, mainly when I have more than one CD to burn and they are just for family use. What scares me the most is burning a copy of a disk that has a plain, general purpose, mailing label on it. Simply playing that disk probably won't see it running at more than 4X, but reading it into iTunes/the hard drive could see it running at the maximum allowed by your reader. I'm not sure how evenly balanced that disk is with a small label way off center.
I don't think Myth Busters used disks like that when they were trying to see how fast they could spin them before they disintegrated...
