Greetings:

The requirements Bean articulated are roughly the same across Canada. I think it has to do with a provision in the constitution that services must be provided in the "minority" language where numbers warrant.

In Ontario:
English Public: Anyone. French classes start in kindergarten or grade 1. Immersion and bilingual programs available from kindergarten on.
French: Mother tongue must be French and at least one parent must have been educated in Canada in French.

In Quebec: Reverse the Ontario case except that they don't have English immersion and they do not teach English before grade 4. Some francophone parents to a case to the Quebec Court of Appeals (think State Supreme Court) to argue for their rights to have their children learn English. They argued that the children's futures were being limited by not being allowed to learn English. If you, as an American, moved to Quebec, you would not be allowed to send your children to English school because you did not go to school in English in Canada. French parents would get around restrictions by sending one child to private English school for one year and thereby get the right to send their siblings to English public schools.

Très compliqué, n'est-ce pas?