[Hali87]

Quebec has always been the primary French-Canadian province (at least since well before Confederation) and over time Quebec has become proportionately less English-speaking while the rest of Canada has become proportionately less French-speaking.

Federal services are offered in both English and French in all of Canada but day-to-day life is really only bilingual in a few cities (Montreal being the primary example). Bilingualism is such a visible part of the country's modern brand though that I can see where the surprise comes from. The relative importance of the French language outside of Quebec varies by province but tends to be stronger in the Eastern half of the country, though not so much in Toronto or the surrounding area.