The successful spread of Christianity was probably mainly down to two things.
Firstly, people didn't really know very much in those days. There wasn't any science to speak of; no-one bothered to sit and figure out why things happened the way they did or why things were the way they were - the issue seldom even occurred to them, as in fact it seldom occurs to many people today. But at least if it occurs to us today we can Google it - or even better, find a book about it by people it's occurred to before who did something about it, and who developed a thing called the 'Scientific Method', which is basically this:
Let's assume that glass has been invented (which I'm informed it had been - thanks Dave-!) and that you have a glass bowl. You turn the bowl upside down and hold it on the surface of a pond. You surmise that, if there is an invisible substance all around you that moves the trees there must be some of it in that bowl, and that if you push the bowl downwards that substance will in turn push the water down. If nothing is there the water will remain level. You do and it doesn't. There is something there. Your curiosity piqued, you then surmise that this stuff must be made up of small invisible bits, so you try the same experiment with a tea-strainer. The water stays level. (At least I'm assuming it does.) You now know that the particles that make up the 'air' as you've decided to call it (by way of thinking 'I think I'll call it... errrr...') are smaller than the holes in the tea-strainer, as they are clearly escaping through it.
This conclusion makes a certain amount of sense because a tree shaking violently in the wind is scary in the same way that having someone bigger than you shout and shake his fists at you is scary. It also saves you having to think about it any more depth and leaves you free to plough your field without having to worry about it any further, except for a nagging suspicion that God is angry because he didn't want you to use that particular field.
So, when monks and missionaries come plodding by with their big bibles, and tell you that you don't, indeed, have to think about all this stuff at all - the answers are all here in this book - how we got here and when; where we go when we leave and why - it seems sensible to pay attention, even if they do have silly haircuts. It feels like an even better idea when they tell you that if you don't happen to agree you'll spend eternity - or at least that part of it that starts when you die - burning horribly while little demons prod your more sensitive parts with forks and laugh maniacally. (It doesn't actually say this in the book, but this is no doubt a mere oversight on God's part.)
So for the next thousand years or so, a lot of people could be seen going into churches and promising to be good, while relatively few people were seen next to ponds messing about with tea-strainers.
And that's how the Dark Ages happened.