Between AD 900 and AD 1200 Vikings, being able to navigate skillfully across the open sea, were the dominant seafarers of the North Atlantic. When the Sun was shining, geographical north could be determined with a special sundial. However, how the Vikings could have navigated in cloudy or foggy situations, when the Sun's disc was unusable, is still not fully known. A hypothesis was formulated in 1967, which suggested that under foggy or cloudy conditions, Vikings might have been able to determine the azimuth direction of the Sun with the help of skylight polarization, just like some insects. This hypothesis has been widely accepted and is regularly cited by researchers, even though an experimental basis, so far, has not been forthcoming. According to this theory, the Vikings could have determined the direction of the skylight polarization with the help of an enigmatic birefringent crystal, functioning as a linearly polarizing filter. Such a crystal is referred to as 'sunstone' in one of the Viking's sagas, but its exact nature is unknown. Although accepted by many, the hypothesis of polarimetric navigation by Vikings also has numerous sceptics. In this paper, we summarize the results of our own celestial polarization measurements and psychophysical laboratory experiments, in which we studied the atmospheric optical prerequisites of possible sky-polarimetric navigation in Tunisia, Finland, Hungary and the high Arctic.