However, I have heard ...that in Québec you must marry in a church, that there is no such thing as a "civil ceremony". And that this somehow accounts for a much higher percentage of common-law relationships in that province

Good gosh no. You don't have to marry in a church. You can get married at the Palais de justice (courthouse I suppose is the accurate translation). Most first-time marriages do occur in church though because of the grandeur of walking down the aisle in that white wedding dress.

Common-law unions...wellll, I think the French have a very open mind when it comes to relationships and having sex. Waiting to get married before having sex went out of style in my parent's generation (and even then). Starting in the 70's it became common-place to live together instead of getting married. There was very little stigma attached to it so it just became an other option.

It is now extremely rare that someone will not be living with his/her future spouse when they get married.

IMPORTANT NOTE: I am talking about *French* Québecers only. Anglophones have somewhat the same mores and allophones not at all.