Foreword: I'm kind obsessed with naming convention, especially after being introduced to CK2 (and flipping table when my Zoroastrian Persian relatives names his firstborn Muhammad). After researching a bit, I realized that early Roman martyrs would be indifferently named after their praenomen, nomen, or cognomen/agnomen. And so I wonder I much has that participated in the slow abandonment of the trianomia to the nomen+cognomen structure with increasingly individual cognomen? And how the Christian faith has influenced in those first centuries the naming process of Roman people?
One thing to understand about the traditional Roman naming formula of tria nomina (i.e. praenomen + nomen gentile + cognomen) is that it was never as rigidly traditional as one might think, nor was it immune to change even before Christianity. To get it out of the way, by the time Christianity had gained significant influence in the Empire and Christian practices began to impact onomastics on a serious level, the Roman tria nomina system - which was always just a transitory state, to borrow a phrase from Salway, Romans had begun with a singular name as well, and even Mark Anthony in the late republic didn't have a cognomen - had already 'broken down', so to speak. This is due to a variety of factors, about which I have written here, and also here. Suffice it to say that the praenomen had almost died out and the cognomen become ever more important; the nomen gentile too lost importance (more than 50% of people shared 8 gentile names, most of them the names of Emperors like Iulius, Claudius, Cocceius, Flavius, Aurelius) and thus began to fall out of use a bit later; filiation and tribus too fall out of use with the general expansion of the Empire and the civitas Romana. With the decline of the praenomen, the filiation became less important (stating the praenomen of the father), and the tribus, too lost its distinctive function since the number of tribus never changed, but the number of people enrolled in them expanded rapidly, especially after the constitutio Antoniniana created so many new citizens at the beginning of the 3rd century (this affects the nomen as well). In short, there was a perceivable trend towards a single-name system towards the late Empire, even before Christianity. Kajanto, in his study about Christian names in Roman inscriptions, summarizes it thus:
The revolutionary changes in the Christian name system were accordingly a consummation of tendencies which were also operative in the pagan material. [Kajanto 1963, 14.]
What, then, did Christianity change? The point where we really can begin to grasp Christian naming culture on a relevant scale comes in the early third century, with the advent of communal burial grounds or catacombs, where we can differentiate Christian dead from the pagan. Mostly through their use of symbols such as the dove, the Chi-Rho (a ligature of the Greek letters X and P for Christus), the anchor or the cross; as well as Christian language and formulas expressing beliefs, customs (such as specifically denoting that a girl died a virgin) and eschatological expectations tied to the Christian vision of afterlife (like 'ut in deo vivant', so that they may live in God). In the early Christian epitaphs, we almost exclusively find duo nomina (family name + cognomen) or single cognomina, with the praenomen being already very rare and a clear trend towards the single name. Singular cognomina are already pretty prevalent compared to the pagan material, which may be a function of Christianity being originally a religion especially appealing to the lower social strata, especially slaves who only had a single cognomen, most often, by origin or custom, a Greek one.
What is interesting is that early Christians show no qualms about using Latin or Greek pagan theophoric names, that is names relating to pagan deities. These are names such as Dionysius, Mercurius, Posidonius, Eros, Vulcanius. Interestingly, these are found even among members of the clergy, which suggests that they had through long use lost their strong association with the respective pagan deities, so that there was no dissonance felt when clerics or lay Christians had names such as these.
So Christianity doesn't really change a lot in the beginning. The trends are already there, and Christians use other markers to express their Christian identity, especially phrases and symbols. However, a few things do change.
What Christianity brings, already in the early stages, is an influx of new names with a decidedly Christian connotation. Individual Christians could always choose a name that was expressively Christian. These names come in several categories. First, these are names connected to Christian concepts, like the trinity of faith, love and hope - Fides, Caritas, Spes, or Pistis, Agape and Elpis, respectively. Names relating to liturgical or eschatological concepts, like Anastasius, from Greek Anastasios, the resurrected one; Refrigerius, relating to the concept of the heavenly communal banquet, or literally 'refreshment'; Martyrius referring to martyrdom; Redemptus, the redeemed one; Renatus, reborn; Paschasius, referring to Easter; Quadragesima, referring to the time of Lent and so on. These names are however quite scarce.
Then you have names that contain in them small phrases relating to Christian faith; f.e. Quodvultdeus, what God wills; Adeodatus or Deusdedit, given by God/God gave; Deogratias, thanks to God; Spesindeo, faith in God. These names were particularly popular in North Africa as well as among immigrants from that region.
Biblical names as well as names of saints and martyrs are another category. These includes names such as Maria, Iosephus, Ioannes, Thomas, Susanna; Petrus, Paulus and so on, but they are both rarely used or not noticably different from the pagan names they originally were (this is especially evident in names such as Paulus and Petrus, or in the biblibal names also common in the Jewish community, so there is no clear Christian connection to make each time they appear.)
Lastly, we have names that were already common among pagans, but either fell out of use or were filled with new meanings by Christians, names such as Felix, Victor, Vitalis or Gaudentius (joy - a central Christian concept); and also names such as Theodora/us or Theophila/us which were as popular with pagans. This is a murky category and you can't tell just by looking at the name whether someone was Christian or not.
Another peculiarity about Christian naming conventions is the disappearance of onomastic markers indicating slave/freedman status. Christianity accepted the institution of slavery as part of the social order, the church was pretty indifferent towards it. In death, in the light of Christian eschatology, it became positively irrelevant, your social status didn't matter as much at the resurrection of the flesh. Thus, name elements such as 'X servus/libertus', slave/freedman of X, became less important. In comparison, these markers are still found in the names of pagans.
What also appears, but not limited to Christian epitaphs, is the use of supernomina or signa added to the cognomen, in the form of 'X qui et (vocatur) Y', X who is also (called) Y or 'id est', that is, 'signo/nomine', (known) by the name of. A popular theory is that these were names taken over on baptism, but as attractive as this theory is, the evidence is only sporadic. Nonetheless, we have examples which clearly spell this out, like in the case of Pascasius (relating to Easter), who was born Severus:
Natus Severi nomine Pascasius / dies pasc(h)ales prid(ie) No<n>(as) April<es> / die Io<v>is fl(avio) Constantino / et Rufo vv(iris) cc(larissimis) conss(ulibus) qui vixit / annorum VI percepit / XI Kal(endas) Maias et albas suas / octa<v>as pasc(h)ae ad sepulcrum / deposuit d(ie) IIII Kal(endas) Mai(as) Fl(avio) Basilio / v(iro) c(larissimo) c[ons(ule)] [- ICVR VI 15895]
'Pascasius, born with the name of Severus, during Easter on the day before the Nones of April (April 4) during the consulship of the illustrious men Flavius Constantinus and Rufus (the year 457), who lived six years. He was baptized on the 11th day before the Kalends of May (April 21) and deposited his eight-day white baptismal robes of Easter in his tomb on the 3rd day before the Kalends of May (April 29) in the consulshp of the illustrious man Flavius Basilis.'
This is a clear reference to a new name adopted during baptism, and in fact, in some other Christian names, we find a clear mention of a break with a previous life. Names such as Proiectus or Stercorius, which literally mean 'thrown away' or 'left among the rubbish' may refer to Christians abandoned by their families and adopted by Christian charity. Alumni, or adopted Children, appear frequently on Christian inscriptions and often bear these kind of names.
In the end, Christianity didn't change much. There were societal forces, which I have glossed over a bit here (though feel free to ask), already at work that led to the regression towards a single-name system when Christianity began to make its mark upon the names people chose. In late antiquity, the system was back to the traditional indo-germanic single-name system (modified by patronymics, honorifics, occupational names or nicknames where appropriate/needed) whence it came and Christian cognomina got absorbed into the onomastic practice same as other pagan cognomina. Christianity might have hastened that change, but what it really changed was the names people used, not much how they used them.
Sources: