King Louis XIV of France decreed in 1669 that New France (Canada) should adopt the French militia system. This required all able-bodied men 16-60 to serve and protect the colony as needed.
During the Seven Year's War (1756-1763) both France and Britain brought trained regiments from overseas to fight for control of the new colonies. When Britain won they kept the militia system in place and with the Militia Act of 1855 introduced a volunteer force who would be paid and uniformed year-round. By the 1880's militias became completely voluntary.
From 1759 to 1871 the British Army had regiments stationed in Canada. They were recalled when Britain decided it was time their colonies had their own permanent military. Two artillery batteries were established at Quebec City, Quebec and Kingston, Ontario where a Military College was established in 1876. An amendment to the Militia Act in 1883 authorized a permanent Military force.
The Canadian Army was founded in 1867, the Royal Canadian Navy in 1910 and the Royal Canadian Air Force in 1924. In 1968 all three were unified as the Canadian Armed Forces.
Military records for Canadians who served are held in different places, depending on when, where and why. Some records are held by the British War Office, some by Library & Archives Canada, and others are held elsewhere.
Links to some records are provided below. This is not a full or extensive list. Many records are also held locally where the regiments were posted so be sure to also check local armouries and newspapers. Nationally there is the Canadian War Museum and the Canadian Virtual War Memorial, as well as CanadaGenWeb's Roll of Honour Project. Internationally there is the Commonwealth War Graves Commission.