I love this idea, but I've been avoiding thinking about it, because it's so complicated. I feel like a [[Category:North America, Historical Geography]] might be the most *accurate* supercategory to hold all the pre-Columbian-through-today subcategories. But it might not be the most obvious place that people would go to find, say, Iroquois Nation, Acadia, or Colony of Massachusetts place names.
It's possible the right approach would be to have the [[Category:North America, Historical Geography]] category. And then, under Canada have a [[Category: Provinces, Canada]] with the modern province names as subcategories. In the hatnote, have a blurb that says something like:
"These categories only apply to Canada after 1867 (1949 in the case of Newfoundland). The modern country of Canada, in the upper reaches of North America, lies in a region with a complex history, and the territory has historically been the site of a number of autonomous regions, and colonies governed by European countries; and a large number of indigenous Nations that held territory before and after 1492. See [[:Category:North America, Historical Geography]] to find the appropriate place names and categories for anyone who lived before Canadian Confederation in 1867"