I have conducted some research on Internet and this is what I found about the Fleur de Lys. I translated word by word from French to English, so please, be indulgent.
Three thousand years ago, this flower was already used by the Assyrians as decoration and emblem. It was then found again in Ancient Egypt (symbol of power), in India, Greece, Rome and Gaulle (ancient country of France which used to include the actual France, Belgium and the North of Italy: I refer you to Asterix and Obelix for more details).
The Lys means “The flower of flowers”. For Greek people, the white Lys was the emblem of the “Universal Creation”. The Lys is to Occident what the Lotus flower is to Orient. The Lys symbolizes Purity. Called the “mariale” flower because dedicated to Virgin Mary (or Mother Mary?), this symbol is divine, pure and virginal.
It is in 507 A.D., under Clovis, first French Christian king that the first Fleur de Lys appeared on a flag. Progressively, we could see it on royal seals and armorial bearings. It is under French king Louis VII that it first appeared on a royal banner. After many years, the Fleur de Lys became the "Fleur du Roi" (The Flower of the King).
I guess we can say that French kings were the first ones to use it as an emblem and symbol in Europe. Since Quebec used to be a French colony (but is no more), I guess this is why it is now our emblem.
Voilà! I hope it could help.