Must pre-nuptiasl agreements made in Quebec, Canada, be executed before a Quebec notary?

If you want it to carry any weight at all, then yes, either a notary or an attorney. Of course, even then, there's always the chance that, when push comes to shove, it won't be worth the paper it's written on.