Where in history did early Christians start to associate Mary with extra-biblical power? Throughout the history of the Catholic church, how has this worship fluctuated and why?
Some corrections before we get going in earnest:
How did Mary, the mother of Jesus, become the center of cult-like worship in the Catholic church?
Two points here. First, the Christian devotion to Mary is a cult in the specific and technical use of the word. That is, it is a religious devotion centered around ritualized behaviors. Secondly, no one worships any saint no matter how popular they are. Saints may be venerated, but to worship them is idolatry. The term "veneration" signifies that you are offering the saint respect but recognizing that the source of their holy power is God.
associate Mary with extra-biblical power
It's a bit of protestant polemic to say that Mary has "extra-biblical power" because it means you take for granted that the Bible is interpreted in a certain way. A Roman Catholic interpretation of the Bible is certainly compatible with Mary's "power". To note once more - no saint has power except by the gift of God.
my basic hypothesis is that Mary achieved cult-status amongst early Christians
This is not so much a hypothesis as it is a fact, although one which is much less evident and which requires substantial localization depending on how you define "early."
Contemporary Christianity and Protestants agree that prayer to Mary is unnecessary and not biblically founded
Many protestant sects will agree with you, but as a blanket statement it is categorically false.
Now that's out of the way, let's get to the heart of the matter.
The reasons why Mary became an exceptionally popular saint and intercessor in Roman Catholicism are so numerous and intricate there is no way for me to address all of them here. The Christian emphasis on virginity, the particular way Mary satisfied certain spiritual needs, and the support of certain powerful and vocal ecclesiastics are all among the contributing factors. There are many excellent books on the subject, and I would look at work by Carolyn Bynum, Amy Remensnyder, and Rachel Fulton Brown, among others, if you want to dig deeper. Here, I'm going to focus on one of the larger components.
Although this may seem at odds with what you have been told, women are extremely important to Christianity in the first four centuries of its existence. Most of the modern conversation focuses on women in liturgical roles which leads to a murkier and more varied picture, but women, and in particular wealthy women, were some of the main benefactors of the early Church. In late antiquity, following the model of the Empress Helena, the mother of Constantine the Great, this long tradition of female benefactors became subsumed into the role of the queen.
By the sixth century, after the western Empire had fallen and the Merovingians and Lombards ruled in their place, the queen was the merciful counterpart to the king. Where a king would wage war, order executions, and pass judgment, it was the queen's prerogative to dispense mercy, give alms, and, most importantly, to release prisoners. This understanding of queenship far outlasted the middle ages.
Paralleling the relationship between Constantine and his mother Helena, Christ rules heaven accompanied by his mother Mary. One of Mary's titles in the Roman Catholic Church is "Queen of Heaven" and this has always been understood in a very literal fashion. Mary is the queen par excellance, and she maintains all the attributes associated with her lesser earthly equivalents. Just as a mortal queen could order a man justly sentenced to die be freed from his captivity and punishment, Mary, by her relationship to Christ, could ensure that a sinner, justly doomed to an eternal death, was likewise freed from the consequences of his crimes. Mary's role as forgiving queen is most evident in her many miracles which involve the salvation and redemption of wicked and undeserving men and women.
From the beginning of the development of the cult of saints Marian devotion was never really unpopular, but it only became extremely so in the high middle ages. There are, again, nearly infinite reasons for this, but one among many is a man named Bernard of Clairvaux (d. 1153). Bernard was a Burgundian noble who in 1113 joined a newly-founded and reform-minded Benedictine monastery at Cîteaux in central France. By 1115, Bernard was abbot of his own monastery at Clairvaux, and the fledgling Cistercian order exploded across Europe, growing to over 350 monasteries by Bernard's death. Bernard was not technically the head of the Cistercian order - that honor fell to the abbot of Cîteaux - but he concentrated on its expansion. He entered the mainstream of ecclesiastical politics for the first time in 1128 when he argued for the creation of the Knights Templar in his book De laude novae militiae - In Praise of the New Knighthood - and he would later help write their Rule. Two years later Bernard proved a pivotal voice in rallying support behind Pope Innocent II in a papal schism, and he was soon seen as the one of the most powerful and well-known churchmen of his day. When one of Bernard's disciples was elected Pope Eugine III following Innocent's death in 1143, he was more or less the most powerful man in Europe and was often called a "second Pope." Bernard was instrumental in the preaching of the Second Crusade, and the book of advice on the papal office he wrote for Eugine, De consideratione, is still read by popes today.
Bernard, and the Cistercians more generally, were greatly devoted to Mary. Using his power, his popularity, and the popularity of his order, Bernard was instrumental to the popularization of Marian devotion in the West. At the same time, there were vast cultural forces on the move. Scholars generally draw a line between two "forms" of medieval piety, a split which occurs roughly somewhere between 1215 and 1250. To paint a really rough picture, tied in with an increased clerical emphasis on lay religious education, most noticeable in the decrees of Lateran IV in 1215, religious experience was shifting out of the domain of the upper classes and spreading into the broader population.
This later medieval piety was profoundly concerned with individual sinfulness and the impossibility of redemption. As an illustration, I have personally read late medieval indulgences which offer the remittance of 46,000 years of purgatory for saying a sequence of prayers, and it is important to note that this would be considered a drop in the bucket. Now, remember the role of the queen in pardoning the guilty? And remember that Mary was seen as the highest queen, able to perform the same tasks on a cosmic scale? Is it any wonder, then, that she was the object of such intense devotion?
Some reading:
Vauchez, André. Sainthood in the Later Middle Ages. Cambridge: Cambridge University Press, 1997.
Brown, Peter. The Cult of the Saints: Its Rise and Function in Latin Christianity. Haskell Lectures on History of Religions 2. Chicago: University of Chicago Press, 1981.
McNamara, Jo Ann, John E Halborg, and E. Gordon Whatley, eds. Sainted Women of the Dark Ages. Durham, N.C: Duke University Press, 1992.
Bynum, Caroline Walker. Holy Feast and Holy Fast: The Religious Significance of Food to Medieval Women. The New Historicism : Studies in Cultural Poetics. Berkeley: University of California Press, 1987.
Huizinga, Johan. The Autumn of the Middle Ages. Chicago: University of Chicago Press, 1996. (Read with caution and skepticism)
It seems like this is a loaded question and goes against the rules of the subreddit. Catholics do not worship Mary any more than Protestants worship John the Baptist, Lutherans worship the saints, or Moslems worship Muhammed.
I'm going to take a different tack to /u/telkanuru and talk about some of the doctrinal developments in relation to Mary in the early period, and some of the sources for later Catholic understandings of Mary.
The main distinctives about the Roman Catholic church's teaching about Mary include:
The doctrine of perpetual Virginity is the idea that Mary was not only a virgin prior to giving birth to Jesus, but remained so afterwards. You can find early evidence for this kind of belief in the 2nd century Proto-evangelium of James, chapters 19-20. The idea appears widespread by the 4th century, as attested by referring to Mary as "ever-Virgin", for example in Athanasius' Contra Arianos, 2.70. This idea probably developed in tandem with the growing emphasis on virginity and celibacy within the church, you can see that idea already in the aforementioned Proto-evangelium.
The doctrine of immaculate conception states that from the moment of her being conceived, Mary was kept free from original sin, thus receiving the grace that Roman Catholics normally identify with baptism. This doctrine was not formally defined until 1854. As far as I know there is no explicit textual expression of this idea in Antiquity, and Pius IX who decreed it admits the same, that it was not explicitly put forward until the 12th century. For that reason I will leave it alone as outside my field.
Third, Mary was given the Greek title Θεοτόκος, this is often translated as "Mother of God", but a more overly-literal translation might be "the one who gave birth to the one who is God". The title refers to the fact that, because of the understanding that in Jesus there are both divine and human natures, distinct yet indivisable, but there is only one person, anything that is predicated of one nature is predicated of the person. This means that because Mary gave physical birth to Jesus, she gave physical birth to the one who is God. It does not mean that Mary gave birth to God. I realise this paragraph is probably difficult to follow, but that's because 5th century theological debates are technical and precise.
There is some evidence of the use of this title in the 4th century, but it becomes important in the 5th century debates over Jesus' two natures and how the relate. This is the conflict between Nestorius and Cyril that results in the Council of Ephesus in 431 and the Council of Chalcedon in 451.
The last major doctrinal distinctive of Roman Catholicism in regards to Mary is the Assumption, that is that Mary at the end of her earthly life was physically "taken up" into heaven, similar to Enoch in Genesis of Elijah in 2 Kings, though the exact formulation of those two events within RC theology is not something I am familiar with. The earliest text that explicitly affirms this is The Book of Mary's Repose, which survives in an Ethiopic translation, from no earlier than the 3rd century; there are also some traditions in Syriac from the 6th century. It's not entirely clear how this assumption took place, in that the Orthodox view is that Mary died and was raised 3 days later and then taken up into heaven. This is a possible understanding of the RC view as well. Anyway, it's not attested within the early church in Greek or Latin, and so again that puts it outside my expertise.
There are other issues to consider, especially the growing role of saints as intermediaries, of Mary in particular, of veneration of saints and prayer directed via saints to God, but I will leave that aside for now.