Here are some ideas:
-- The Roman Empire survives as a united Empire due to a relatively early POD that still isn't too early to prevent Christianity. Naturally, the earlier you go, the more likely it is to somehow affect the basic development of Christianity. Views differ on how early certain tenets were acually more or less established, and on how likely the mainline orthodoxy of OTL was to succeed against various competing branches. That is: some think 'Roman' Christianity was likely ro become successful anyway, others think a more 'Alexandrian', gnostic sort of christianity could easily have gained the upper hand in an ATL. If you're of the opinion that something very much like that Catholic Church, with Pope and all, was in fact established early (hi Saint Peter!) and estimate its odds of succeeding as very good, then you can probibly justify a very early POD. This would be best to give Rome the best chances. (My favourite POD for this is Drusus Germanicus not dying and eventually succeeding Augustus, but that would probably affect early Christians considerably...)
No matter the POD, the idea is that Rome can then expand over time. Its greater success goes hand-in-hand with the stability and success of Christianity, which eventually becomes the state religion. As a consequence, early heresies are dealt with quite effectively, and we see a Catholic influence in places as far east as Babylonia-- where this influence was Nestorian in OTL. Islam is probably butterflied away, and Arabia may in fact become Christian instead. If we assume that the Roman Empire becomes the world's foremost power, it can then expand its faith quite aggressively. Centuries down the line, the Roman Empire has triumphed over Persia, which is shattered into mostly Christian successor states. Rome is industrialising. It has discovered, colonised and converted the Americas. With no Islam, central Asia is likewise Christian, as is Indonesia. Missionaries are hard at work in Africa, India and the Far East.
Even after Rome eventually fractures as an Empire... the religion stays. If we assume that a central part of successfully dealing with early heresies is more tolerance for local 'rites', you end up with a decentralised Catholic Church. Various regions and peoples have their own rites and various minor differences, but they agree on the important points of doctrine. Little fuss is made over the details, as long as the various branches of the Church stay loyal to the Holy See. (Which, enjoying rather geat autonomy anyway, they do-- since making trouble isn't worth it.)
This is probably your best bet for overall success. Fix things early on, and you prevent most problems before they arise, Schismatics and Protestants don't ever become an issue, and Islam gets butterflied. You win by default. I can see there being between four and five billion Christians by the present day, all (or nearly all) part of an undivided Church.
-- Somewhat unlikely and possibly entirely apocryphal, but let us assume for the moment that it is either historical, or it somehow becomes historical: Charlemagne marries Irene of the ERE, or some other dynastic re-unification of West and East is undertaken. This gets the full blessing of the Pope, who actually performs the ceremony etc. This construct would be extremely shaky, but assume for the moment that it survives its early weakness, that the interaction between the two greatly benefits both economically and knowledge-wise (exchange of whatever philosophical and scientific sources they each possess). The capital must no doubt be in Rome, and the Empire will be very decentralised by default. Some balance gets struck between the caesaropapist tendencies of the ERE and the papal supremacy of the West (illustrated by the fact that the Pope crowned Charlemagne, thus positioning himself as more elevented than the Emperor). The compromise rather ends up like the outcome of OTL's investiture struggle: the Pope enjoys supremacy, but temporal matters are the Emperor's business.
The union of west and east prevents the Great Schism. Likewise, with most of Christendom united in one Empire, it becomes rather likely that various outlying places (British isles, Scandinavia etc.) eventually become part of this empire, if only in a theoretical sense. There were times in OTL where kings of England recognised the Holy Roman Emperor as the supreme temporal authority over all Christendom-- with the caveat that they knew it was 'only on paper'. Just build on that. The restored Roman Empire theoretically covers all of Christendom, and even states like Ireland and Poland recognise the Emperor as their liege... but much like the Chinese Emperor for the greater part of history, whoever sits on the throne will know that this authority exists only on paper. He controls his imperial core, and the outlying regions mostly defer to the Emperor as supreme arbiter in diplomatic disagreements and things like that. At times his power waxes, at times it wanes.
But no matter what, Christendom has an Emperor. It has a Pope. And both Empire and Church, covering such a sprawling multitude, are by definition rather decentral. Again, this would ultimately just aid the Church in preventing schisms. As in OTL, Europeans are quite likely to end up discovering, colonising and converting the Americas. If this united Empire can pull it off, North Africa and the Levant might be permanently reclaimed from the hands of Islam. From there, Chistianity can expand into Africa. Elsewhere, it can go steadily east from european Russia, seeping towards the bering Strait and eventually covering the area of OTL's Russia.
This is ultimately less effective than the scenario suggested above. Supplanting Islam in Africa and the Levant gets you some extra souls, but mostly, we're talking about "just" making sure every Christian remains with the mother church. I'd estimate the result in the present day at c. 3 billion Christians, all (or nearly all) part of an undivided Church. That's a big achievement, but not an absolute majority of the world's population.
-- Having political history go pretty much as in OTL is also an option, if you can just get the Church to be more tolerant of local rites. This wouldn't do much early on, but could prevent the Great Schism, could see england opting to devolve into an "Anglican Rite Catholicism" rather than split off, and could also forestall the Reformation entirely (reforming your local branch of the Church would be the easier course, instead of trying to overturn everything). Best outcome there, however, seems to me that pretty much all Christians remain in the mother church. That gives you "merely" an estimated 4.5 billion Christians by the present day.
All in all, having a single religion constitute an absolute majority of all humans isn't easy at all. Naturally, there are PODs like a reverse "Years of Rice and Salt", with a plague wiping out vast swathes of the population in parts of the world that aren't Christian, but I consider that kind of POD to be a bit unimaginitive.
