I found an interesting document on this topic as regards countries currently using the euro:
http://ec.europa.eu/economy_finance/articles/euro/documents/elteg_en.pdfMost countries mentioned in the report have no penalties for defacing/destroying notes or coins. However:
Belgium: Defacing a coin or note punishable by 1 week to 3 months prison and/or a fine of EUR 26 to 1000.
Ireland: Melting down a coin punishable by fine up to IEP 5000 (EUR 6343.87) and/or up to 2 years in prison.
Cyprus: Fine of up to EUR 1708 for "defeaturement" of notes or coins.
Malta: UP to EUR 1500 fine for any alteration to a banknote.
Slovakia: Up to 6 months prison for damaging the national legal tender.
The report suggests that such penalties would not normally be brought against an individual if the act was done for artistic purposes, for personal (non-exchange) uses only, and not in large quantities of notes/coins.
My suggestion is that if you're going to promote Bitcoin on circulating paper money, obtain a large quantity of the smallest denomination note commonly circulated. Mark these up and keep a small number of them with you for payments. Don't present more than one or two of them in any retail transaction. Use the smallest notes because they draw less scrutiny at retailers, and because they're the most likely to be returned to other customers as change (writing on CA$50 notes is cool, but acceptance of them at retail generally means that only the retailer and a bank clerk will see them before they get returned to the central bank for destruction and replacement). Experiment with colors. Contrast is best for getting the message spread, but if retailers are consistently refusing your bold red text on light blue notes, try a color that doesn't clash with the rest of the note's color scheme.
I think I'll order me a rubber stamp...