I found this interesting tidbit on the Canada Government website.
Here's what they have to say on the matter:
"The name “Canada” likely comes from the Huron-Iroquois word “kanata,” meaning “village” or “settlement.” In 1535, two Aboriginal youths told French explorer Jacques Cartier about the route to kanata; they were actually referring to the village of Stadacona, the site of the present-day City of Québec. For lack of another name, Cartier used the word “Canada” to describe not only the village, but the entire area controlled by its chief, Donnacona.
The name was soon applied to a much larger area; maps in 1547 designated everything north of the St. Lawrence River as Canada. Cartier also called the St. Lawrence River the “rivière du Canada,” a name used until the early 1600s. By 1616, although the entire region was known as New France, the area along the great river of Canada and the Gulf of St. Lawrence was still called Canada.
Soon explorers and fur traders opened up territory to the west and to the south, and the area known as Canada grew. In the early 1700s, the name referred to all French lands in what is now the American Midwest and as far south as present-day Louisiana.
The first use of Canada as an official name came in 1791, when the Province of Quebec was divided into the colonies of Upper Canada and Lower Canada. In 1841, the two colonies were united under one name, the Province of Canada.
Leading up to the proposed confederation, a number of names were suggested for the northern half of the continent of North America, including: Albertsland, Albionora, Borealia, Britannia, Cabotia, Colonia, EfisgaFootnote 1, Hochelaga, Norland, Superior, Transatlantia, TuponiaFootnote 2, and Victorialand.
The debate was placed in perspective by Thomas D’Arcy McGee, who declared on February 9, 1865:
“I read in one newspaper not less than a dozen attempts to derive a new name. One individual chooses Tuponia and another Hochelaga as a suitable name for the new nationality. Now I ask any honourable member of this House how he would feel if he woke up some fine morning and found himself instead of a Canadian, a Tuponian or a Hochelagander.”
Fortunately for posterity, McGee’s wit and reasoning – along with common sense – prevailed, and on July 1, 1867, the provinces of Canada, Nova Scotia, and New Brunswick became “one Dominion under the name of Canada.”"
1. A combination of the first letters of England, France, Ireland, Scotland, Germany, and Aboriginal lands.
2. An acrostic for the United Provinces of North America. An acrostic is a composition in verse of an arrangement of words in which the first, last, or certain other letters in each line taken in order, spell a word or a phrase.
Directly Quoting from Source: http://canada.pch.gc.ca/eng/1443789176782