Typically sharpie is the way to go

However, for our wedding we gave music cd's to all of our guests of all of our wedding songs.. and we used the sticky labels on them

Worked pretty well too!
I've even used the cd in my car cd player (slot load of course) and no problems.
can't remember what software we used.