I'm not sure if you're after a "how" answer, or really asking "why", but either way condensing 400 years of church history into a Reddit thread is not easy.

The first phase of Christian expansion would be in the 30-50 years after the death of Jesus (which I am dating to 33AD). His immediate disciples had some kind of experience that caused them to believe that Jesus had risen from the dead, an expectation that had messianic and eschatological connotations for 1st century Jews. Shortly after they began vigorous efforts to spread their core message about Jesus as the Messiah awaited by the Jews. The author of Acts presents his narrative structured around a theological pattern of showing how that message extended first to Jews, then to Samaritans, then to Gentiles. The evidence of the NT documents strongly supports the idea that Paul became the most prominent and active spreader of the Christian message among Gentiles, so that probably by no later than 70AD there were new Christian communities across Asia Minor, Greece, and to Rome.

The earliest suggestion of concerted persecution is by Nero, as mentioned in Tacitus’ Annals, 15.44, in which Tacitus says that Nero blamed the Great Fire on the Christians; it’s Tacitus who says that Christians were disliked.

Over the very large course of 100-325 AD Christianity spread both geographically as well as growing demographically. This was despite (or in some accounts, because) of periods of persecution. Those persecutions were sporadic, even when they occurred by imperial decree, because local implementation always depended upon attitudes of local rulers. However as early as the Pliny-Trajan correspondence (112 AD) we see that authorities considered merely being a Christian to be a crime punishable by the state, independent of any other ‘actual’ wrongdoing.

Part of that hostility was that Christians were, in Roman eyes, athiests who did not worship the gods, and the interplay between religious and imperial ideology meant that failure to engage in worship was an act of civic anti-socialism and treasonous to the state. That interplay between religion and imperial ideology was the reason that the means of persecution under, say Decius (249-251) and Valerius (253-259) was making offerings to the gods.

However within Christianity a growing ‘theologisation’ of the role of martyrs and martyrdom probably helped transform persecution from a negative to a positive force. People will often harden under opposition, and within 3rd century theology (Cyprian, for example) martyrs were the heroes of Christianity, demonstrating heroic resistance and imitating Jesus in the most intimate and noble way. Martyrdom became an ideal.

The hypothesis that Christianity grew among predominantly slaves and women, while appealing, is almost certainly false. In the case of 1st and 2nd century Christianity, the work of E.A. Judge has been instrumental in showing that Christianity penetrated the social elites. A study by Salzmann in 2002 estimates that in the late 3rd century 10% of the Senatorial class were identifiably Christian.

Stark makes two arguments based on appeal to women. Firstly he notes the prominence of women in Christianity, which he then matches with socio-demographic data to suggest that it lead to both (a) higher fertility rates among Christians than pagans, and (b) conversion of men through marriage. I am not in a good position to evaluate these arguments though.

On the other hand, accounts that Christian acts of charity were instrumental in the popularity of the new faith are likely to be true. Within the Greek philosophical traditions ‘mercy’ was not rated highly as a virtue, since it offended the idea of justice. In this way, though to a lesser extent than ‘humility’, ‘mercy’ emerged as a distinct Christian concept and found expression in practical care of orphans, widows, and the sick. The Apostolic Constitutions (although dated to late 4th century) gives instructions for the deacons about how they are to be dedicated to works of charity among those in need.

Demographically Stark offers a model that suggests growth of 3.4 percent a year, starting with 1000 Christians in 40AD, and a reasonable broad consensus of 6 million around 300 AD (10% of the population). Stark compares this to the growth rates of Jehovah’s Witnesses and Mormons, both groups with high conversion efforts. It also aligns with intermediate ‘milestones’ of demographic projections.

As well known and written about, the conversion of Constantine at the Milvian bridge, however it is parsed, represents a decisive turning point. After this, Constantine begins to favour Christians, and with the Edict of Milan extends religious tolerance. By 350 more than half the Empire are probably Christian, and its social standing has changed remarkably. By Theodosius in 379, a large majority would be Christians, and Theodosius moves Christianity from de facto religion of the Empire to ‘Official Religion’.

Further reading:

As far as Judge goes, I would start with "Social Distinctives of the Christians in the First Century", which is a collection of key essays.

For an indepth scholarly account of the history of the early Church, W.H.C Frend Rise of Christianity

For demographic growth and appeal of Christianity, R. Stark The Rise of Christanity

edit: left out a name in the bibliography. added some line breaks.

edit 2: Thanks to whoever gave me gold! Much appreciated!!

Edit: I didn't see all of /u/talondearg's answer (didn't refresh the page); a good amount of what I mention is already explained well there.

The baptism of the persecutions ("the tree of the church watered by the blood of the martyrs" of Tertullian) has already been mentioned a bit, so I'll offer a few different suggestions.

Early catholic (as opposed to gnostic and judaic Christian sects) Christianity had several things going for it as an ideology. Most of these notions were important elements of other religious and philosophical systems at the time, but Christianity was the first significant synthesis:

Universality: Two senses: the religion claimed to be (and overwhelmingly was) open to any and all serious converts, and Christianity was seen as the fulfillment of all religious seeking. The various appealing aspects of Judaism, its monotheism, morality, and antiquity which a notable minority within the Graeco-Roman world were attracted to, were expanded beyond the national/ethnic borders of Israel by Christianity. It claimed to be a religion within which there was no social distinctions. Men, women, slaves, patricians, rich, poor, etc from any cultural background were, ideally, understood as equals in a theological and eschatological sense. This had great appeal in Roman society where citizenship and the privileges and protections that were limited by a host of factors, upwards of 45% of the population of the empire were slaves, and substantial religious and philosophical explanations for the nature of the world and the human condition were practically limited to the educated elites. Christianity sought converts from anywhere it could, and used local cultural explanations for why it was the system any particular person was looking for. There was dogmatism, but because the content of the doctrines were derived from experience in the world and the church's interpretation of the various scriptural narratives in their historical situation, many elements from those situations could be incorporated into the belief system. The doctrine that Christianity was the religion the world was waiting for was well developed by Christian intellectuals by the 3rd century (see Justin the Philosopher's notion of the "seeds of the word" and Origen of Alexandria's notion of "pillaging the Egyptians") and is evident as early as Paul's epistles.

Judaic Monotheism: Tendencies toward monotheism or henotheism were in vogue in the first century among the highly educated. The Judaic flavor was believed to have considerable antiquity by surrounding cultures (e.g. Judaic religion was deemed a licit religion within the Roman Empire despite the political and insurrectionist tendencies found among many Jewish groups of the time). The Roman and Persian worlds were eras in which antiquity or claimed antiquity of a establishment or belief system demonstrated the value and respectability of whichever establishment. In addition to the assumed antiquity of the religion, following the developments of Judaic theology in the post-exilic period (uncompromising monotheism, the ultimate nature of God, the emphasis on divine interaction with the world and the selection of the Israelites as a significant people among peoples) and the interaction with Greek philosophy (mostly Platonism which helped in formulating the terminology and clarify the concepts used in both the Hasmonean and Roman periods of Judaism and early Christianity) the Judaic God was one of the "biggest" deities around in terms of theological descriptions and supposed ontological descriptions. Transcendence and immanence, creatio ex nihilo, supreme status beyond being as usually described— the only other God concept as elaborate in the vicinity was that of Middle Platonism, from which, as alluded to above, Christianity borrowed vocabulary. There was mutual influence between Christianity and Platonismfor the first thousand years of the common era—see the development of what modern scholars call Neoplatonism and the Christian theological tradition that developed in Alexandria, Egypt.

Emphasis on Historicity: Christianity broadened the Judaic emphasis on the historical reality and continuity of religious experience. Christians, like the Jews before them, were entering into a covenant with God historically. There's tremendous psychological power here; one is directly connected to the works of God (the one, all-powerful, transcendent God) in history, both the history of the Israelites, the incarnational economy of Jesus, and in the growth of the church via the working of the Holy Spirit. There's a particular point of focus in the recent past for early Christians to which they were able to feel connected to. Unlike other divine savior figures of the time, Jesus was clearly understood as historical in the normal sense: located in a particular area, at a particular time, interacting with the world as a historical person would. Heck, he supposedly still had family (descendants of siblings and cousins) alive into the 5th century. One could go to Jerusalem, Bethlehem, or Nazareth and feel certain that this man walked in those places. Not so much with Mithras, Dionysios, or Orpheus. The world he lived in was the world you live in, and your bishop could prove it via his supposed succession from Jesus' disciples. The gods of the Greeks were both less accessible and smaller; the One of the Platonists was unaccessible by any everyday means.

Emphasis on Orthodoxy: Common Graeco-Roman religion was focused on orthopraxis (proper practice of rituals) and not so much on orthodoxy (correct belief). This was well and good for many, but the offer of definitive divine truths is appealing once you're made aware of it. Plenty of other philosophical schools made similar kinds of claims, but Christianity was more accessible to the uneducated. Prior to the Roman adoption of Christianity, there were clear orthodoxies concerning particular theological positions (some universal, some regional). That definitiveness is an attractive quality.

Inclusivity, Exclusivity and Communion: Certain elements of early Christianity bear some resemblance to the practices and rituals of a few Graeco-Roman mystery cults. While it's not right to call catholic Christianity a "mystery cult" (Christianity was radically inclusive in terms of people and radically exclusive of particular actions and beliefs) at any point in its development, components of its practices fulfilled the same social and psychological roles. Rituals/mysteries of initiation (baptism and anointing) and communion (liturgical eucharistic celebrations) date back to the first century and provide a sense of mystical inclusion within the Christian worldview. Various types of individual and communal prayer, liturgical practices, asceticisms, and confession practices satisfied many psychological and existential needs of 1st - 4th century peoples. In Roman antiquity, religion was generally divided into three spheres: public, mystery rites, and philosophical schools. Public rites and celebrations provided a sense of belonging in the greater community, mystery rites provided a more intimate and mystical sense of communion and link with the divine, and philosophy attempted to satisfy intellectual needs and desires. Practically all people participated in public events, and most who could (had the right connections) were initiates in a mystery cult. Philosophy was for the educated elites. Christianity both had elements that fulfilled all these needs and prohibited its adherents to partake of any other religious practices. This exclusivity functions to emphasize the significance of being part of the Christian group: what the Christians are doing is so important and unique that anything else is a cheap imitation. Those who became significantly devoted (a rarity among Graeco-Roman polytheists, but considerably widespread in early Christianity) were more likely to stay in the group and more likely to want to bring others in as well.

Balancing Apocalypticism and Social Concerns: Christianity was unquestionably an apocalyptic sect in the middle of the first century. The end of the world as coming any day now; you were living in the most significant of days. There's a necessity for one to respond immediately to this notion if you take it seriously— and many Jews of the time did. Along with this apocalypticism, Christianity still greatly emphasized Judaism's concern for social justice. Christians need to live in the world, need to do good in the world, need to follow God's commandments in and for the world. This made the religious more compatible with Roman society than a sectarian apocalyptic movement would be. Once the apocalyptic momentum slowed by the 2nd century, a philosophy of long term teleological significance of transformation of society was slowly developed. The Epistle to Diognetus (2nd century) tried to portray Christians as the ideal citizens who go beyond the standards of the Roman law. Christians were reported to have risked life and health for all in their communities during the Plague of Cyprian in 3rd century North Africa. Origen of Alexandria (writing in the early 3rd century) looked to a future of a Christian political situation, in which the government of the world (the Roman Empire) would be an instrument of God through which the whole world would be evangelized and the wisdom of the world would supplement Christian understandings. The conversion of Constantine was celebrated by educated Christians of the 4th century, but it was not entirely unexpected. The Christian historian Eusebius of Caesarea interpreted the conversion of Constantine as the fulfillment of Origen's hopes.

The first probable reason for the spread of embryonic Christianity was that the Apostles went out and disseminated it across the Roman world. The letters of Paul were a testament to this, he was writing to Christians in Ephesus, Corinth and other places, showing that by the end of the first century Christianity had established itself in small communities across a large part of the Hellenised world.

Christianity at these times (60-100 AD roughly) Christianity had a messianic character to it. There was a general consensus that the apocalypse was just around the corner and that the Christian would be saved. This made those that had already converted less likely to convert back, even in the face of intense persecution.

Christianity embraced both women and slaves. With a message of salvation and redemption Christianity was able to convert with relative east groups without a serious stake in the political system, such as women and slaves.

All the doctrine about what Jesus was like and the trinity etc had not been properly hammered out. The great ecumenical councils where the church finally figured out what it believed had not been held yet. This allowed surprising amount of regional variations in what Jesus was perceived to be like. For instance in some early mosaics he is shown as a young beardless man reminiscent of Apollo. At other times he was shown as Sol Invictus crowned with the sun.

Christian festivals were set around the same time as festivals in the traditional Roman calendar. For example Christmas, the birth of Christ was set as December the 25th. Saturnalia was around the same time and started at December 17th, a week long revel where masters pretended to be slaves and slaves masters.

The obvious turning point for Christianity was when Constantine converted to Christianity after the battle of the Milvian Bridge. For the first time Christianity had an official role in the state and it wasted no time making itself one of the organs of the state.

There followed a period of consolidation where Pagans were slowly edged out. Their feast days were made work days and blood sacrifice was banned. The coup de grace of this was in the Theodosian decrees between 389 and 391 which essentially made paganism illegal by closing down all the temples. That is not to say that paganism just died out. It faded slowly with some resurgences and survived in remote part for many hundred years after Theodosius. But we can say with some certainty that Greco-Roman paganism was dead by 1000.

The Christians were not hated!! the persecutions of them were infrequent at best. Nero needed a scapegoat to blame for the great fire of Rome in 66. Decius was insecure on his throne and needed Roman morality to prop him up and Diocletion's persecution was quite ineffective, only 3000 died, and very unpopular with the people. Indeed most of the time Christians were protected by the law against persecution by the authorities.

edit: the date of Saturnalia is December 17th