Canada's Church Records
There is no central repository for church records, if they still exist they are held by the church, the church archives, or the province / territory archives.
Another challenging factor in the search for church records is Canada's history and geography. Some provinces only recognized certain religions. For example, in what is now Ontario only the Anglican church was permitted to perform religious ceremonies from 1763 until the 1790s. If you wanted your marriage to be recognized, you had to marry in the Anglican church regardless of your faith.
Some areas were under-represented and settlers had to use whatever church was closest for them, even if it wasn't their religion. Some religions charged fees for their services and settlers unable to pay may have chosen a church of a different religion that offered free services.
Some churches had circuit ministers who travelled the country tending to the flock. These ministers would travel hundreds of miles performing baptisms, marriages and burial services. Once done their circuit they would return to their home church and it is there that the records would be stored. So your ancestor may have lived in one province and the church records may be in another.
There are some church records online at FamilySearch and Ancestry, and some genealogy societies have transcriptions available. But if the church records you seek are not amongst the easy to find, you will have to do some old-fashioned leg work.
For province, territory or region-specific church records, see the GenWeb site that covers that area.