Two of the most famous references to cats in Old Norse literature are to the fact that the goddess Freyja drove a chariot drawn by two cats, and to the catskin trim of the hood and gloves of the travelling Greenland prophetess in Eiríks saga rauða. At first glance, these seem fairly straightforward. As the expression 'it's like herding cats' reveals, it's pretty hard to get cats to do anything at all, let alone pull a chariot containing a well-upholstered goddess, so the implication is that only someone with supernatural abilities could possibly have a cat-powered wagon. And as for the Greenland prophetess, it's obvious she is just weird, and you would be well-advised to keep your pet kitties away from her for their own safety. But there may be more to both of these references than meets the eye. And yes, the photo is of a stoat, not a cat.
In that still-indispensible reference work Kulturhistorisk leksikon for nordisk middelalder, Johan Bernström argued that, in both of these instances, the word köttr refers not to the domestic cat, felis catus, but rather to the stoat, mustela erminea, and I think this suggestion has much to recommend it, though I do not often see it cited. The white coat of the stoat in winter (pictured below) is the source of that highly-desirable fur known as ermine, and the Eiríks saga reference explicitly states that the prophetess's kattskinnsglófar were hvítir innan ok loðnir 'white and furry on the inside'. She also had a hood lined with kattskinn hvít 'white catskin'. White cats are not that common, and it seems to me much more likely that the extraordinary outfit of the prophetess was made even more spectacular by the addition of ermine.
Similarly, though the other case is much less clear, it seems to me more likely, given the status of ermine, that Freyja's wagon would be said to be pulled by the animals that provide such a noble fur.
The archaeological evidence for when exactly cats were introduced into Norway and Iceland is not very clear, and a recent MA dissertation on the subject has not to my mind fully clarified the matter (it's also pretty wonky on the literary sources). There is plenty of scope here for further study. But it seems clear enough that cats were introduced to Norway before the Viking Age, and that they followed the migrants to Iceland in due course - as confirmed by the recent discovery of a cat's jaw in a burial at Ingiríðarstaðir - and presumably to Greenland. Stoats, however, did not cross the Atlantic, at least not alive, though their furs must have done.
The odd thing is that the modern Norwegian for stoat is 'røyskatt', ON hreysiköttr, a secondary formation based on the comparison with a cat. This doesn't necessarily mean cats came first, just that stoats must also have had another, earlier name which we now don't know. But there is an interesting reference in Orkneyinga saga, when Earl Þorfinnr persuades Kálfr Árnason to fight on his side against Rögnvaldr Brúsason by saying that he doesn't want to be skulking sem köttr í hreysi while Þorfinnr fights for their freedom. What does this mean? A hreysi is either a 'cairn, heap of stones' or a 'cave' of some sort, in general a rocky place. And stoats are known to live in rocky clefts and crevices (though they have a whole range of habitats). Stoats are not native to Orkney, indeed the first intruders had to be forcibly removed from there only last year, but the expression could derive from Norway and be proverbial. So I do think there is a stoat allusion there, even though the Penguin translation of Orkneyinga saga gives 'like a cat in a cave'. Have you ever seen a cat in a cave?