While Luke indeed points out in his Gospel that Joseph was of the house of David,1 it is curious why this was of importance to the narrative, since Jesus was conceived without the seed of Joseph. This led many early Christian Church Fathers and scholars to propose that Mary is also of the house and lineage of David.2 From here several hypotheses emerged to explain this tradition, two which I'll address. But first we should look at what (if anything) we can glean about Mary's parents from history before analyzing the Gospel accounts.
Joachim and Anna
Early theologians and scholars believed that Mary was born to Joachim and Anna as a result of fervent prayers in their old age.3 The evidence of such an early account is clear in the pseudepigraphical Protoevangelium of James, which gives the following (summarized) account:
"In Nazareth there lived a rich and pious couple, Joachim and
Hannah. They were childless. When on a feast day Joachim presented
himself to offer sacrifice in the temple, he was repulsed by a certain
Ruben, under the pretext that men without offspring were unworthy to
be admitted. Whereupon Joachim, bowed down with grief, did not return
home, but went into the mountains to make his plaint to God in
solitude. Also Hannah, having learned the reason of the prolonged
absence of her husband, cried to the Lord to take away from her the
curse of sterility, promising to dedicate her child to the service of
God. Their prayers were heard; an angel came to Hannah and said:
"Hannah, the Lord has looked upon thy tears; thou shalt conceive and
give birth and the fruit of thy womb shall be blessed by all the
world". The angel made the same promise to Joachim, who returned to
his wife. Hannah gave birth to a daughter whom she called Miriam
(Mary)."4
Early Christianity taught that Mary was consequently presented to the temple and had made a vow of virginity (which would then be the reason for her protest to the angel in Luke 1:34). If this is true, the significance is that Jesus of Nazareth came "from both a royal and priestly family."5
While a pseudepigraphical work such as the Protoevangelium of James is not a reliable source for such historical information (the account is likely highly embellished), it does show the presence of similar myths in this time period and assumes the reader's familiarity with the characters, which lends credibility to the notion that these are the names of Mary's parents.6
Matthew gives Joseph's genealogy, while Luke gives Mary's
Καὶ αὐτὸς ἦν Ἰησοῦς ἀρχόμενος ὡσεὶ ἐτῶν τριάκοντα, ὢν υἱός, ὡς
ἐνομίζετο, Ἰωσὴφ τοῦ Ἠλὶ (Luke 3:23, NA28, emphasis mine)
Jesus, when he began his ministry, was about thirty years of age,
being the son (as was supposed) of Joseph, the son of Heli...
(Luke 3:23, ESV)
The NET translators point out concerning the translation of this text,
The parenthetical remark as was supposed makes it clear that Joseph
was not the biological father of Jesus. But a question still remains
whose genealogy this is. Mary is nowhere mentioned....
Advocates that Luke gives a matrilineal genealogy argue that the parenthetical clause (ὡς ἐνομίζετο) is misplaced in this text and that it should instead be translated:
"... being a son (as was supposed of Joseph) of Eli."
One such proponent of this view in history was Thomas Aquinas,7 who argued that the text calls Jesus a son of Eli without explaining why (he likely presumed his readers' familiarity with Eli.8
Luke gives Joseph's genealogy, while Matthew gives Mary's
This view is much less common than the former, but it has been observed throughout Christian history. Clement of Alexandria expressed this early view, writing,
"And in the Gospel according to Matthew, the genealogy which begins
with Abraham is continued down to Mary the mother of the
Lord."9
Victorinus of Pettau also believed this, declaring,
"Matthew strives to declare to us the genealogy of Mary, from whom
Christ took flesh."10
There is no support for this in the extant Greek manuscripts of Matthew, but proponents of this view believe the text has been corrupted and that Matthew originally referred to two Josephs: one being the husband of Mary and the other her father (this is also used to explain the discrepancy with the Lukan account and why the number differs on 14 vs. 13 generations), the idea being that scribes introduced the current reading in order to correct the (apparent) mistake.11
Conclusion
Readers familiar with this controversy would do well to note that I did not address the so-called levirate marriage theory (as well as several other minority perspectives). The levirate marriage theory essentially states that the geneology gives the legal, rather than physical, lineage due to Yibbum. I decided to only address what I believe are the main two scholarly perspectives.
So to summarize my answer, the presence of existing accounts of Mary's Davidic lineage in early Christian history led to the adoption of these views and the formation of later explanations (and legends) based on these accounts, a couple of which have been explained.
1 cf. Luke 1:27.
2 Jaroslav Pelikan. Mary Through the Centuries: Her Place in the History of Culture. (New Haven, CT: Yale University Press, 1998), 24-25. Specifically, cf. St. Augustine and later in history, Annius of Viterbo, who both made similar propositions concerning the lineage of Heli/Joachim/Eliachim.
3 Specifically St. John Damascene, St. Gregory of Nyssa, St. Germanus of Constantinople, and St. Fulbert of Chartres.
4 Frederick Holweck, "St. Anne." In The Catholic Encyclopedia. (New York: Robert Appleton Company, 1907). Retrieved January 15, 2014 from New Advent: http://www.newadvent.org/cathen/01538a.htm. An astute reader cannot help but see the similarity with the biblical account of the birth of Samuel, which casts significant doubt on its historical reliability. The translated text of the Protoevangelium of James can be read here.
5 cf. Aug., Consens. Evang., l. II, c. 2
6 For those who object to claims that these are the names of Mary's parents solely because "the source is pseudepigraphical," it should be kept in mind that such works often reflect an existing tradition and incorporate it into a legend (as likely happens here), but they do not generally originate the tradition. Rejecting the existence of historical figures because of later legends written about them is the equivalent of assuming Abraham Lincoln is a fictitious character on the basis of the movie, Abraham Lincoln: Vampire Hunter (I must give credit to Mark Shea for this witty response to such a line of thinking).
7 Thomas Aquinas, Summa Theologica, p. IIIa, q.31, a.3, Reply to Objection 2.
8 The name here rendered 'Eli' has numerous alternate spellings in the manuscript tradition, but most of them are limited to a few manuscripts. Depending on the manuscript used and language being transliterated from, this name may be written as Eli, Heli, Joachim, or Eliachim. However, there are some who argue that 'Eli' in this text is not synonymous with Joachim / Eliakim (on historical grounds, not philological ones).
9 Clement of Alexandria, Stromata, 21. Also notable is that Irenaeus refutes this view in Adversus haereses, 3.21.9.
10 Victorinus of Pettau, Apocalypsin, 4.7–10.
11 Harold A. Blair, "Matthew 1:16 and the Matthaean Genealogy", Studia Evangelica 2 (1964), 149–154.