In very short answer, the majority of the Scandinavians possibly except for those who lived in now Sweden (especially in middle-Sweden called Svealand as well as some borderland areas) in the middle to late 11th century had accepted Christianity as a basic value within their society for at least more than a generation (ca. 30 years). Thus, I suppose that those who were pronounced non-Christians were hardly found in Harald's invasion army (if not entirely extinct).

As I wrote an answer to the similar question, not a small number of the Vikings, especially in the 11th century, were actually Christians, and being Christian itself did not stop the act of notorious brutality of the plunderers at once, as testified by the torture of some English clergy during the invasion of Sweyn Forkbeard of the Danes in the beginning of the 11th century as well as Magnus Barefoot (grandson of Harald hardrada)'s temporary harrying over the northern part of the British Isles in the end of the 11th century.

It is also worth considering to what extent the organization principle of the 11th century Scandinavian royal fleets like Harald hardrada's invasion or the Danish fleet of Sweyn and Cnut the Great, i.e. the 'Viking army' of the second Viking Age, in fact shared the basic characteristic of the 9th century Viking bands.

References:

• Berend, Nora (ed.). Christianization and the Rise of Christian Monarchy: Scandinavia, Central Europe and Rus’ c. 900-1200. Cambridge: Cambridge UP, 2007.
• Anne N. Jørgensen et al. Maritime Warfare in Northern Europe: Technology, Organisation, Logistics, and Administration 500BC - 1500 AD. Copenhagen: PNM, 2002.

There are several, interconnected reasons why.

1. Harald followed the two "Missionary kings" of Norway: Olaf Tryggvason and St. Olaf (who was canonized in 1031, immediately following his death. Additionally, he is almost a century after Hakon the Good, who was the first Norwegian king to be Christian (even though he was buried as a pagan, according to the skaldic poem Hákonarmál, written by a personal friend of Hakon). As a result, being Christian was by this point, certainly, not a reason to reject an otherwise good ruler.

Additionally, there had been regular, often peaceful contact between Norse pagans and Christians since the reign of Charlemagne. Many Danish and Norwegian traders who traded goods in Christian countries (be they France or down to Miklagard, i.e. Constantinople) were "prime-signed"; i.e. they were marked as having started to convert so that it wasn't blasphemy for Christian merchants to trade with them. (Anders Winroth, The Conversion of Scandinavia). By the 11th century, this had developed to most/all of Scandinavia being at least nominally Christian (Iceland adopted Christianity in the year 1000, according to Ari Thorgilsson in Islendingabok.) In practice, there was some overlap and syncretic beliefs lingering, but the "Vikings" of this time period were mostly Christian themselves.

2. Religion seems to have been important in Norse Scandinavia, but not that strong of an ideological force. Though local lords were also priests (the word godi means "chieftain" in the Icelandic sagas, but it more accurately means "priest"), Sverre Bagge argues that the polytheistic and decentralized nature of Pre-Christian Nordic Religions provided no impetus for individuals to unify under a single banner. As such, there was no competing religious hierarchy to prevent pagans from following a rich, Christian ruler. (From Viking Stronghold to Christian Kingdom. State Formation in Norway, c. 900-1350)

Following this, power in the Viking Age was usually accumulated through feasts and gift-giving, not religious language. If a chieftain was generous with food and treasure to his followers, that would increase reputation far more quickly than religion did (Vidar Palsson, Language of Power: Feasting and Gift-Giving in Medieval Iceland and Its Sagas).