Rome is officially Christian which makes Britain officially Christian, the problem is that there is very little evidence to work on, so any reconstruction might be based upon a small handful of people. The countryside is probably more pagan than the urban areas, but even in the urban areas there is little evidence (see here for a contestable church in Silchester).

There are 3 to 4 varieties of Christianity in Britain.

1. The first is indigenous British Christianity. We know this from Gildas (who complains about the clergy and how they were not doing their job), and from the Synod of Arles (314AD) who mentions 3 British bishops - so Christianity is episcopal in nature, as St Patrick complained. But we also know that the spread of Christianity isn't total, as York and London had no bishop.

2. The second are the Irish monks, who come over to Britain on their own account (not sent by the pope). They worked with the Picts in Scotland and the English pagans, and had a series of reasonably sized monasteries under the work of St Colomba (521-597AD), primarily at Iona, but others around Ireland and Scotland too.

3. There are monastic orders. The 4th century Saint Martin had monastic orders all over Britain, and St Dyfrig continued this mostly in Wales, building a significant number of churches so that most people were only a couple hours away from one. Bede (731AD) mentions that there were 2000 monks at Bangor-is-Coed, which is short hand for 'a lot', and he mentions numerous other monasteries that we only know they exist because he said so.

4. You've then got the Conversion of Britain as in the sources (the Anglo-Saxon Chronicle but also Bede). The easy version is Pope Gregory's famous story about calling them 'Angels' (instead of Angles) comes into play, and that's possibly the start of the Augustinian mission in Britain, which doesn't do terribly well. In fact, it's Pope Honorarius sends off Birinus (ignoring the Augustinian mission already there) in 634AD, who appears to start off the Conversion in Wessex (which according to the ASC is the most important place after all ;)) If you want the slightly harder version, more academically we have the about 5 stages of conversion which run as follows.

5. Kent becomes Christianised under Pope Gregory's efforts, somewhere around 597-616AD. This isn't terribly well received, especially by Saeberht's sons who drove the bishop from the kingdom.

6. A second wave of conversions in Kent, East Saxon/East Anglia from about 616-625AD.

7. A third wave between 625-642AD, in Kent, Wessex, East Anglia, and Northumbria.

8. A fourth wave between 654-664, mostly sponsored by Northumbria (who wields the largest political clout), and as a result the East Saxons, Middle Anglians, and Mercians convert. The last pagan king, Penda, dies in 650AD, and the Northumbrian King Oswiu calls the Synod of Whitby in 664AD which decides that they're going to follow the Roman, rather than Ionian liturgy.

9. Between 670-680s, the Isle of Wight and Sussex and converted.

And that's the end of paganism in Britain as far as we know.

Most parts of Britain were (officially) Christian by the late seventh century. But how they got there is complicated.

There's ongoing uncertainty about the extent of Christianization in Roman Britain. Before 410 (and possibly for some time after that), Britain was integrated into the rest of the Roman empire and we have some limited archaeological evidence of Christian art appearing on the island. Roman elites in Britain by the end of the fourth century must have been largely Christian (following trends across the empire), but it's always very difficult to say how far down these beliefs go into the lives of the 'average' person.

Then the Romans leave Britain, and our textual sources dry up, mostly.

From the fifth through seventh centuries, we only really have one good text surviving from Britain. Interestingly, it's a Christian sermon in Latin, and its style is pretty typical of a well-educated Roman preacher. But we also have a lot of new, strange burial practices that sometimes include things like magical ammulets and animal sacrifice. We also see a reappearance of cremation burials, which historians have long associated with 'pagan' religions. When writing appears again in the late seventh and early eighth centuries, people like the churchman Bede (writing c. 730) begin talking about the dominance of pagan religions which were only driven back after Rome sent missionaries to England c. 600.

So the traditional narrative built from the archaeological and written evidence has tended to present different version of a story in which Christian Roman Britain is overwhelmed by paganism for about 200 years, after which it slowly (re)converted to Christianity in the seventh and eighth centuries. The most popular version of this story (dating to the 1870s, and very influential since) has been that Christian Britains were driven into Wales by invading Saxon immigrants from Germany who brought with them a pagan, Germanic faith in Woden (Odinn), Thor, etc. Bede (the churchman writing in the eighth century) says this invasion was very violent, and was sent by God as a judgment on the Romano-British because they had failed to evangelize like good Christians ought. Some historians (like Frend) have wondered if Christianity didn't spread to ordinary people in Britain, and disappeared when Roman authority was withdrawn from the island in the early fifth century. Archaeologists have spent a lot of time looking for Christian churches, and they're difficult to find during this period (though several important sites do appear to have been in use during much of this period, so Christianity was probably not entirely eliminated during this period).

Then, the story goes, Pope Gregory the Great sees some slaves from Britain, realizes they aren't Christian, and sends Augustine - a close associate and fellow monk - to Britain to found a monastery associated with the household of Bertha (a Christian from Francia, married to King Aethelberht of Kent). Aethelberht eventually converted to Christianity, but this church remained somewhat localized until other kings further north began to convert in the mid seventh century. Archaeologists and historians of ealry medieval England usually divide English history around this century of conversion, and associate a lot off social changes (like changes in burial practice) with the gradual Christianization of the population. That's the story of how England became Christian as you'll see it in most textbooks.

But here's where things get messy. Most of the evidence for the story above is actually very problematic, and many studies in the past three decades have undermined most of its points individually. The big story remains largely unchanged, because it's really hard to throw out the structuring narrative for 200 years of history, but it's becoming increasingly difficult to carry on as though the problems with this story don't exist. I'll briefly outline the issues, and sum up my personal views on this topic.

First of all, the archaeology. It's generally assumed that fifth-seventh century archaeology shows strong evidence for paganism replacing Christity, for a few reasons. People are, first of all, buried with a lot of stuff in their graves (weapons, jewelry, food, etc). These 'furnished inhumations' have been characterized as pagan for several reasons, including the suggestion that the weapons and food might show belief in Valhalla, and the assertion that Christian priests didn't approve of burying dead bodies with lots of stuff. A recent study (Hoggett 2010) argued that you can see communities converting to Christianity when these practices end. This is problematic, however, for a few reasons. There aren't any textual references to Valhalla until hundreds of years later (like, the 13th century), and we have no reason to believe that weapons in graves imply belief in a warrior afterlife. In fact, just across the English Channel Merovingian Christians are being buried with weapons. And the church not only didn't say anything again these kinds of burials; they actually weren't very involved in burial at all until the ninth century (see Effros 2002, Rebillard 2003, Halsall 2010 for more on this). So furnished inhumations don't actually have a real connection to paganism; they are, in fact, how Christians are buried right next door in France.

Cremation burials are also often cited as examples of a pagan practice. While it's true that Christians strongly favor not burning bodies, however, nearly every church father who discusses cremation agrees that there's nothing specifically harmful that results from a Christian's body being burned (God, they all agree, can gather up the ashes at the resurrection; see Rebillard 2003 for a thorough discussion of the sources). It's only in the Teutonic crusades in the high middle ages (again, more than half a millennium later) that cremation becomes explicitly condemned as a pagan practice. So while these cremation burials do look different from what most Christians are doing, there's nothing to suggest they're explicitly pagan.

(continued in the comment below)