Q:

Did people use to marry much younger during the last millennium? 

I've frequently heard it stated that "people used to marry at much younger ages" historically.   Recently, these kinds of statements have tended to show up in sociological discussions about young people choosing to get married later.   Many such studies tend only to trace data back through the 20th century, often stopping at 1960 or so, when age at first marriage was particularly low. 
In historical studies of marriage, the more common statistic seems to be the "age of consent" for marriage, which was often lower than today.   But those numbers tell us little about the average age that most people married. 
I've come across a few references here and there which have tried to measure actual marriage ages historically, and they often seem to come up with numbers that are perhaps surprisingly higher than we might expect.   For instance, in 17th-century England Wikipedia notes that a survey of 1000 marriage certificates showed the average age for brides was 24 years and 27 years for the grooms.   I've seen a number of other sources which have indicated that first marriage ages were often in the early to mid-20s in parts of Western Europe in the past few centuries.   (Obviously, this can vary significantly by region as well as time period.) 
Based on data like this, my sense is that our perception of young marriage ages has been skewed by selection bias: we know more about aristocratic families, and they tended to arrange marriages at particularly young ages for political reasons. 
Moreover, at least for the U.S., it seems we may have met a local minimum of median age at first marriage in the 1950s, if these statistics derived from census data are to be believed.   
Data like this has made me wonder if our perception of younger marriages on average is a historical myth (or at least needs significant qualification), perhaps based only on our perception that parents and grandparents may have married younger on average than current generations.   But were the mid-1900s actually historical outliers, or at least part of a more complex picture? 
IN SUM: Prior to the last century or so, what evidence do we have for the statement "people used to marry at much younger ages," in general?  Some historians have asserted that people even used to marry basically upon reaching puberty; is there evidence to support or debunk such claims?   Obviously there are plenty of historical examples of marriage at a young age, but does that also relate directly to a similar trend in median marriage ages (or not)?   
Since marriage records, legal issues, and customs in Western marriage have varied by time and region over the past 1000 years or so (i.e., since the beginning of some regulation and standardization of Western marriage), do we even have enough information to speculate on such general trends over time?   How much variance is in the data?   And if we can observe any broad trends, what are they? 
(I realize the answers here may vary significantly by region.   I'm particularly interested in Europe, as well as the U.S./Canada, but data on other regions could be interesting as well.) 

EDIT: I've edited the question somewhat to try to make clear what I'm asking for here.   I do NOT expect a general history of world marriage ages over the past 1000 years.   (However, if anyone can point to a reputable external resource that surveys such information, that would obviously be a superior contribution toward answering this question.)   I began the question with a common historical claim about an overall marriage trend, and I'm interested in whether actual historical data supports that claim in general -- OR whether there are other general trends, or whether it's all so inconsistent that we can't make any useful general observations. 

A:

Not really. 
Generally speaking, most European women since married in their early to mid twenties, to men in their mid to late twenties.  The age gap for the commoners, i.e. the vast majority of the population, were typically not large.  Unfortunately the question declined to define how much younger is "much younger" supposed to mean, but most Europeans married well after the onset of puberty.  
Overall, there does seem to be an upward trend in marriage ages.  However, we have little statistical evidence prior to the 17th century.  The paucity of records makes claims of trends over the whole millennium rather hazardous.   

Both spouses married late in Europe during the Early Middle Ages.  Citing Carolingian survey data, the late David Herlihy argues[1] that prior to 1000 or so, barbarian marriage customs - marrying in late twenties to similarly aged spouse - predominated in Western Europe.  From about A.D. 1,000, however, the value of women appears to have declined.  Rather than receiving a bridal price from the husband, families now paid dowries to unload daughters much earlier.  The age of first marriage for women thus plummeted to their late teens, but largely left that of men unaffected.  
For reasons that remain unclear, the situation began to be reversed at some point during the High and Late Middle Ages.  This gave rise to the curious nuptial phenomenon known as the northwestern European pattern, which has dominated Western Civilisation to this date.  Proposed in his highly influential 1965 work[2] by John Hajnal, this paints a picture where both spouses married late and established their own households, independent of their parents.  Another feature is that significant proportions of both men and women abstained from marriage completely.  Under Hajnal's classification, this system prevailed west of an imaginary line running from Trieste to St Petersburg.  
Hajnal's pattern is sometimes thought to originate from the value of retaining a daughter's labour on Late Medieval farms of Western Europe.  Later on, the habit of young women and men to work in other households also delayed marriages.  This contrasts with the Mediterranean situation, where domestic servants were more likely to be married and widowed.  Other arguments propose that the need for financial security (due to the habit of relocating away from home upon marriage) forced delays. 

Data from the Middle Ages are scarce, the earliest statistical records from the Late Medieval and Early Modern periods demonstrates a relatively high, and increasing, age at first marriage.  By the Late Middle Ages Dijonese women were known[3] to marry at 20.  This rose to 21 during the 16th century, and everywhere in France the mean age of first marriage seemed to have climbed to about 25 by the 18th.  
Similarly, in most German regions, women married in their twenties - averaging between 22.7 to 28.5 in one study[4].  Demographic data from the late 17th century[5] reveal that commoner women from Giessen and Heuchelheim on average first married when just over 24, although Mainz's average was much lower at 21.3. 
Likewise, Medieval English couples are thought to have married during their their early to mid twenties[6].  By the Early Modern period, the average 17th century English women were marrying when 25.6-26.2 to men 28.1 years of age, although it declined slightly subsequently. 

In the Netherlands, by the middle of the period, the mean ages at first marriages for women were estimated to be about 20-21 at mid 16th century Leiden, and 23.5-25 at late 16th century Amsterdam.  Both groups married husbands who were on average 1-2 years older.  These numbers further increased after the 17th century. 
Overall, the evidence is that European marriage patterns resembles that of the 20th century. 

Not all of Europe followed the same pattern.  Southern Europeans women were more likely to marry young to older men, although ages were generally still around 20.  A landmark study[7] of 1427 Tuscany reveal the mean age of first marriage there to be 19 for women, but 28 for men. 
Subsequent studies[8] on 15th and 16th century Florence confirms that all women married when 18 to 19, to men between 27.7 and 31.2.  However, men with higher socioeconomic status tended to marry older, a trend not reflected in women's marriage patterns. 
While the Florentine situation is often regarded as unusual, it is not unique.  Another study[9] of 15th century Ragusa showed that women were on average betrothed at 18, but gave birth to their first child when 22.  From this the authors surmised that Ragusan couples consummated their marriages when the women were 21 and men 36.  In this case, local cultural norms seemed to be the main culprit. 

Nuptial patterns in colonial North America were also different from the colonists' Western European motherland.  A lack of eligible women relative to available bachelors resulted in fierce competition for potential brides[10].  This led to a reduction of women's age at first marriage in the 17th century, though it gradually caught up to European norms as the colonies grew over the following centuries. 
However, few colonial couples marry as young as earlier writers had once assumed [11].  In early English colonies, the average age at first marriage for women were late teens to very early twenties[12], roughly five years lower than that of England.  In Massachusetts[13], women married around 19 to 20 in the early 17h century.  Maryland women married even younger at 17 to 18, while for Virginians it was closer to 21[14]. 
The difference during the early colonial period is much smaller for men, who married mid to late twenties in the colonies.  This was only a couple of years lower than that of English men.  Mirroring developments in England, the gap in ages between spouse closed overtime.  Women's age at first marriage climbed back up to almost 24 by the 19th century, while men's dropped slightly to around 25-26.  In both cases, the mean age of different colonies evened out over time. 

Many cultures elsewhere in the world did have lower marriage ages than contemporary Europeans.  For instance, Song China at the start of this period had legal minimum ages of marriage set at 16 for men and 14 for women.  A survey[15].  of tomb inscriptions found on average, women married when slightly over 18 to men slightly over 23.  Similarly, in Japan during the early modern period, women were found[4] to have married around 16.7 to 22.7.  By the late 18th and 19th centuries, especially in areas of high commercial development, women's mean age of marriage had rose to around 22-25[16]. 

References:
[1] Herlihy, David.  Medieval Households.  Harvard University Press, 1985. 
[2] Hajnal, John. " European Marriage Patterns in Perspective." ( 1965): 101-43. 
[3] Rossiaud, Jacques. " Prostitution, jeunesse et société dans les villes du Sud-Est au XVe siècle."  Annales (1976): 289-325. 
[4] Murayama, Satoshi. " Regional Standardization in the Age at Marriage: A Comparative Study of Pre-industrial Germany and Japan."  The History of the Family 6.2 (2001): 303-324. 
[5] Hurwich, Judith J. Noble Strategies: Marriage and Sexuality in the Zimmern Chronicle.  Vol.  75.  Truman State Univ Press, 2006. 
[6] McSheffrey, Shannon.  Marriage, Sex, and Civic Culture in Late Medieval London.  University of Pennsylvania Press, 2006. 
[7] Herlihy, David, and Christiane Klapisch-Zuber. "[ Tuscans and their families: a study of the Florentine catasto of 1427]."  Editions de lEcole des Hautes Etudes en Sciences Sociales Ouvrage 8 (1985). 
[8] Siegmund, Stefanie Beth.  The Medici state and the Ghetto of Florence: the construction of an early modern Jewish community.  Stanford University Press, 2006. 
[9] Rheubottom, David B. "“Sisters First”: Betrothal Order and Age At Marriage in Fifteenth-Century Ragusa."  Journal of Family History 13.4 (1988): 359-376. 
[10] Haines, Michael R., and Richard H. Steckel, eds.  A Population History of North America.  Cambridge University Press, 2000. 
[11] Lancaster, Jane Beckman, and Beatrix A. Hamburg, eds.  School-age Pregnancy and Parenthood: Bisocial Dimensions.  Transaction Publishers, 1986. 
[12] Smith, Daniel Scott. " The Demographic History of Colonial New England."  The Journal of Economic History 32.01 (1972): 165-183. 
[13] Demos, John. " Notes on life in Plymouth Colony."  The William and Mary Quarterly: A Magazine of Early American History (1965): 264-286. 
[14] Wells, Robert V. "The population of England's colonies in America: Old English or new Americans?."  Population Studies 46.1 (1992): 85-102. 
[15] 〈宋代婚姻禮俗考述〉方建新《文史》第24輯158頁, 1985 April
[16] Saito, Osamu. " The Third Pattern of Marriage and Remarriage: Japan in Eurasian Comparative Perspectives."  Marriage and the Family in Eurasia: Perspectives on the Hajnal Hypothesis (2005): 165-193. 

A:

Others have already provided excellent information and cites.  There are a couple other things to look at. 
There may actually be a proxy that you can use to fill in data that you can't directly obtain: the number of children a woman bears should be related to her marriage age.  The larger the family size, the younger the marriage age.  Another proxy might be the length of one generation (which would indicate the average age of the mother when having any of her children).  Finally, a proxy you could use is when property (farms etc.)  was passed through the generation.  In many regions, they were passed on only from father to the firstborn son, which would give you a good indication of the age of the father when he had his first child, and thus indirectly of the marriage age of men (of course, daughters as first children would be a confounding factor here!) 
In central Europe, you also will have a hard time going back 1000 years with your research, because the 30 years war (1609-1639) destroyed most relevant records, if they were even ever collected. 

The definition of marriage itself has changed multiple times over the last millenia. 
Marriage wasn't always the formal recorded matter it is today, and in some cases it may not even have been one-man, one-woman. 

Based on data like this, my sense is that our perception of young
  marriage ages has been skewed by selection bias: we know more about
  aristocratic families, and they tended to arrange marriages at
  particularly young ages for political reasons. 

I think you may actually be subject to another selection bias of your own: most marriages weren't recorded until, IIRC, around the 16th to 19th century, depending on the region.  In medieval Europe, what we today would call "shacking up" was the very definition of marriage - you were married when one partner moved in with the other, and maybe your family or the church held festivities for the occasion. 

The purpose of marriage has changed multiple times. 
Marriage could be for love. 
Marriage could be for political reasons (not just in the higher levels, but potentially even at the village level). 
Marriage could be for procreation. 
Marriage could be for social security. 
Marriage could be for mutual protection. 
Marriage could be for division of labor. 
Different purposes would lead to different optimum marriage ages. 

Biological factors play a major role. 
People, and in particular women, have a limited age range when they can procreate.  When maximizing procreating (whether for its own sake, or to have many children providing social security) was the goal of marriage, that would argue for an earlier marriage age. 
Infant mortality would also call for women having more time for plenty of pregnancies. 
Maternal mortality would probably call for higher average marriage age.  Very young mothers would be at higher risk (and people would have known that). 
Today, we are probably near the upper end of the age range where marriage for procreation purposes is feasible at all, and then only with very small family sizes.  That would support the notion that historically, people did marry younger (although it does not say how much younger). 
Marrying late is, in a way, a luxury.  During times of turmoil or disease, people would have children (and thus marry) as early as possible.  During times of peace, prosperity, and longevity, people could afford to wait longer.  Incidentally, it seems that @Semaphore's data also follows the same general pattern: a higher average marriage age in wealthy Florence, for instance, and it seems that generally the higher marriage ages seem to correlate with peaceful periods. 
Based on all of that, you will probably find the following patterns:

Average marriage age varied with conditions, both up and down. 
Average marriage age among unrecorded marriages are likely to be lower than among recorded marriages (because ordinary people had less security and more need for many children). 
Today's average marriage age is likely near the historic peak. 

Incidentally, one way to validate this is to look at international comparisons today.  Today's developing countries may have their own issues, but in many ways, especially when it comes to the basics of humanity, very much resemble medieval Europe.