I’ve heard this many times but can’t find much evidence. What evidence is there, and how did this come to be a common belief?
The idea came from the article Cats and commerce by American geneticist Neil B. Todd (1936 - 2014), published in Scientific American in 1977. Todd compiled previous research about feline phenotypes around the world (many of them collected by himself) and mapped the relative proportions of cat coat colours by alleles. Todd does not provide references in this paper, but previous articles by him and other authors give an idea of the methodology. In a study of cat genetics done in Boston, Todd sampled cats found in animal rescue shelters, experimental facilities, and veterinary clinics (Todd, 1964).
Here is the map in Cats and commerce obtained for the "sex-linked orange allele", which gives the phenotypes tortoiseshell, calico (both usually female only) and marmelade (orange). The remarkable thing about this map is its odd distribution with three disconnected geographical areas: Northern Europe, Eastern North Africa (and Sicily/Southern Italy), and Asia Minor. The fact that there is a drop off of the phenotype around Asia Minor suggests that the allele did not spread beyond this region by land.
Todd also noted the higher presence in those areas of "dominant white" cats: he found this significant as white cats are both attractive and more fragile (reduced viability), which points to human interference, ie people chose to own those white cats and their presence was not random. Unlike the orange map, the maps of the other two alleles (non-agouti and blotched tabby) studied by Todd are relatively more contiguous: the blotched-tabby map is clearly centered on Western Europe and the non-agouti map goes from Morocco to the British Isles.
Todd made the hypothesis that the orange and white cats had been transported by sea (hence their presence in coastal areas of North Africa) from an origin in Asia Minor to Northern Europe:
Could it be that 1,000 years after they were introduced to these last outposts of European civilization cats still reflect what may have been aesthetic preferences of the Vikings? [...] The evidence suggests that the Vikings selectively transported this profile of sex-linked orange and dominant white from their contacts on the Black Sea and planted it in the North Atlantic.
Of course, the idea of Vikings, of all people, being partial to orange kitties and petting them on their drakkars is fundamentally amusing, which certainly explains the lasting popularity of the concept.
Cats may have not been the only critter transported by Vikings: recent studies of mouse mitochondrial DNA (mDNA) have linked Viking travels to the dissemination of mice throughout Western Europe (Searle and al., 2009):
It is our contention, therefore, that for the house mouse the Orkney mtDNA lineage represents a marker for Norwegian Viking influence. It should not be assumed, however, that mice with the Orkney lineage originated in Norway and were taken to the British Isles. The transport may have been in the other direction, but still made by Norwegian Vikings. Our results add to the previously described association between Madeiran mice and Danish Vikings, in indicating that house mice are a valuable proxy for Viking movements, as revealed through the studies of mtDNA. The combination in the Viking period of the spread of urbanization in northwestern Europe and the trade facilitated by sophisticated ships capable of travelling substantial distances and carrying large amounts of cargo make the Vikings ideal house mouse vectors. There is clear evidence from Viking-age deposits in Iceland and Greenland that house mice were indeed transported on Viking ships.
Another paper (Jones et al., 2013) on mouse phylogeography suggests that the analysis of cat and mouse dissemination can serve as "bioproxies" for human colonisation and demographic history. The authors cite the Cats and commerce paper, that they find "intriguing", but note the lack of cat studies done with molecular markers instead of the visual observations of Todd and his colleagues.
Sources