They didn't - not really, at least. The conversion of the Scandinavians took about four hundred years, starting with the mission of Hamburg-Bremen, and Willibrod going to Denmark some time between 710 and 718. He was...less than successful in his attempt at converting the Danes, and for the next hundred years or so, further attempts met with very little success.

What started to change things for Denmark was that, in 826, king Harald Klak was forced to flee by his co-king, Horik I, and took refuge in at the court of Emperor Louis the Pious. While there, he asked for military assistance against Horik and Louis agreed, but only on the condition that Harald convert. Harald and around 400 Danes converted and they went back to Denmark, with the monk (later Saint) Ansgar accompanying them to help convert further Danes.

The attempt at broader conversion in Denmark was not as successful as Louis had hoped, and Ansgar later moved his mission to Sweden, arriving in Birka around 829. By 931, the Archdiocese of Hamburg had been established with the express purpose of converting the Scandinavians.

By 860, Ansgar was able to win over king Horik II of Denmark and chapels were established at Hedeby and Ribe. By 948, Denmark had become its own diocese, with Ribe as it's seat, and the conversion of king Harald blátonn around 960 marked a major step forward in the Christianization of Denmark, to the point where he is noted on one of the Jelling rune stones to be the king who "made the Danes Christian." Of course, there were still pagans active in Denmark and resistance to Christian influences, but by the reign of king Canute IV in the mid 1000s, Denmark was fully converted.

Norway's conversion seems to have gone a bit quicker than Denmark's, starting with king Haakon góði around 935. King Haraldr gráfeldr was famed for destroying a number of pagan temples, thus expanding the influence of Christianity in Norway. The next ruler of Norway was Jarl Haakon Sigurðsson, a very staunch pagan, and he resisted a great deal of Christian influence, to the point of breaking an alliance with Denmark because of their attempts to forcibly convert Norway and defeating a punitive invasion by the Danes in 986.

When Óláfr Tryggvasson became king in 995, he began stamping out all traces of paganism across Norwegian territory, including the Faeroe Islands, Iceland, Greenland, Shetland, and Orkney. When he was killed by the Jarls of Lade in 1000, Iceland had already officially converted to Christianity and Sigmundr Breitsson had effectively made the Faeroes Christian by threat of violence.

Óláfs conversion of Shetland and Orkney worked very similar to Sigmunds; in 995, on Orkney, he summoned Jarl Sigurðr digri and said, basically, "Everyone in Orkney will convert or I'll cut off your head." When faced with that choice, Sigurðr converted pretty quickly. Shetland was ruled by Sigurðr and so was converted at the same time.

After Óláfs death in 1000, Norway and the Norwegian territories experienced a pagan resurgence under the Jarls of Lade, but by 1015, when Óláfr digri became king Óláf II, that pagan influence was stamped out.

Sweden was the longest-lasting pagan territory in Scandinavia, with king Sigurðr Jórsalafari leading a crusade against pagans in Småland in 1123 that finally ended the last remnants of pagan worship in Scandinavia.

If you're looking for relatively contemporary info on the conversion of places like Orkney and the Shetlands, I recommend that you check out Orkneyinga saga, and for general Scandinavian conversion, Heimskringla, Óláfs saga helga/The Saga of St. Olaf, Óláfs saga Tryggvassonnar/The Saga of Olaf Tryggvason, and - most crucially for accounts of the conversion attempts in Scandinavia - Adam of Bremen's Gesta Hammaburgensis ecclesiae pontificum/Deeds of the Bishops of Hamburg. Also, you should check out Rimbert's Vita Ansgari for more of St. Ansgar's work in Scandinavia

Nora Berend's Christianization and the Rise of Christian Monarchy: Scandinavia, Central Europe and Rus' c. 900–1200 is an excellent examination of the later stages of Christianization in Scandinavia, and Anders Winroth's The conversion of Scandinavia: Vikings, merchants, and missionaries in the remaking of Northern Europe is another excellent book for you to take a look at.

Edit: Forgot Vita Ansgari, which is super important

One answer to this is, compared to what other cultures?

The people of Scandinavia knew of Christianity for many hundred years before the Viking age. Indeed, some scholars see pagan centres as Uppsala as something of a reaction against Christianity, and that persons from the continent helped creating it. (For an introduction, see online works of Troels Brandt at Gedevasen.dk)

If one wants to, it is possible to look at Uppsala as something like 600 years of defence against Christendom.

But you mention Hiberno-Norse, and they are part of the answer. If you look at other Vikings that settled outside of Scandinavia, you will probably see the same thing. Most probably the amount of settlers were not large enough to maintain paganism; and, even more importantly, those in charge must have felt that they had something to gain by adopting Christianity. The gain being more power in the here and now. Anders Winroth's book uses such an approach to discuss conversion.

If we look at Västergötland, we find Christian cemeteries from the 9th century, and by the middle of the 10th, pagan burials have more or less disappeared. Fifty years later it becomes the centre for Swedish Christian kings.

There are many different ideas about how this came about, some say that Christianity spread from the bottom up, but actual cemetery evidence might say the opposite. Here one can note that one of the earliest Christian cemeteries - Varnhem - is a place where the elite had lived for hundreds of years. It would go on to be a Cistercian abbey, and the burial place for at least four rulers of Sweden. (For thoughts about this, see Claes Theliander, Västergötlands kristnande...)

There are other examples of cemeteries and churches at places for the elite. In Swedish they are called a gårdskyrka, a church built for a farm/manor, and probably with a single patron behind it.

We do not know who ruled Västergötland at the time, but the connections with Denmark are very obvious, and it is reasonable to guess that the elite took part in numerous raids. From later ages we know they did. Presumably they found that being Christian gave them chances both at home, and abroad.

Christian influences did not only come from Germany and England. We know that Vikings were serving in Greece, and historians like Tore Nyberg and John Lind have been thinking about that, discussing something they call varjagisk kristendom, or Varangian Christendom.

If we look at Uppsala it is obvious that it continued to be a centre for paganism for a long time. According to tradition the temple was not destroyed until the end of the 11th century. Economical factors were important in the process, but those that came to dominate Scandinavia probably already had connections with the Continent. What happened was that the change in the east made Uppsala less of a centre, and that must have made it easier for Christianity to grow around Mälaren.