OK - A little research.
It does have to do with the Federal/Provincial structure in Canada. In particular, the Federal government has no powers in family/probate/etc. law. Those powers belong to the provinces, and the there is no so-called "Federal State Clause" in the BNA act (what was the constitution in 1961) or the 1982 constitution. As a result, the Federal government cannot bind the provinces to do anything in that domain as part of a treaty. I believe that the "Supremacy Clause" of the constitution acts as the "Federal State Clause" in the US (that's a guess).
It appears that there's a movement to get Canada to sign that treaty somehow.
Here are some references:
Blog entry about Apostilles in Canada - (read the comment by John Gregory)
which points to
A section in a Google Book of an International Law book
Original Post follows (the wild/educated guess version):
Canada has two legal systems for non-criminal law. Quebec civil law is based on the French Napoleonic traditions. In every other province, law is based on the traditions and rules of British common law. They are very different (a simple example, the word "notary" has a very different meaning in Quebec than it does in the rest of Canada or in the US (perhaps excluding Louisiana)).
In addition, getting this to work would require the cooperation of all of the provinces (and in particular, Quebec). Getting an agreement like this in place may not be worth the effort and (political capital) expense. Never under-estimate the complications of getting the federal government and all the provinces to agree to something in Canada.