Before the lack of statistics, only a general guesstimate can be done. It's usually tought that the eastern part of the empire had a important Christian population at this point, when it was more isolated in the western part (more urban, for exemple).
Not that it point out a real unity of Christians, the edict of Thessalonica being as well made against organised roman religion than arianism.
Basically more eastern, more urban, more meditteranean, more likely to have Christianism being dominant if not demographically, at least socially.
While the overall proportion of Christians was probably minoritary (in the beggining of the century, depending of the provinces it's something from 33% to 5%), it's certainly the majority of many urban centers, stations of the imperial power (basically, where it's important, where imperial elites, bureaucrats, etc. lives)
It's to be noted that it's essentially an imperial act, rather than the Church puppetizing the empire and "using the imperial power". It's basically the other way around. Theodosius search an unifying factor for his dominion, and Christianism seems to be the more fitting universalist belief widely present in imperial and honestiores circles of the East.
The part of sincere faith can't be ruled out, but the political implications are still clear.