The witch's cat is as much a part of her traditional paraphernalia as her pointy hat and broomstick. Terry Pratchett's Nanny Ogg wouldn't be quite the same character without her formidable tom-cat Greebo:
Under the table, Greebo sat and washed himself. Occasionally he burped.
Vampires have risen from the dead, the grave and the crypt, but have never
managed it from the cat.
--Witches Abroad
The logic of the association is clear enough. Cats can move silently, they often hunt by night, and a well-camouflaged tabby or black cat can give the impression of having materialised out of nowhere, all characteristics that fit easily with the supernatural. Superstitions about cats abound to this day, which would fit with them having once been closely associated with magic and the supernatural. The association with deities is very old; in Ancient Egypt, several goddesses were associated with cats and depicted as cats or with cat heads (see the Pitt Rivers Museum website for examples). But how far back does the association between cats and witches go?
In The Secret Middle Ages, Malcolm Jones cites a record from 1324 of an Irish witch, Alice Kyteler, whose demonic familiar could take on the form of a cat. Shape-shifting, in which the witch herself turns into a cat, is mentioned by Gervase of Tilbury in 1211, "women have been seen and wounded in the shape of cats", and by the late fifteenth century illustrations of witches frequently show them with cats (p. 40). So the association was firmly established by the Middle Ages.
In Norse mythology, the goddess Freyja rode in a carriage drawn by cats, according to the Icelandic writer and historian Snorri Sturluson. Snorri was writing in the thirteenth century when the Norse pagan religious beliefs were dying out, and is usually credited with wishing to record the old traditions before they were lost for ever (for which modern scholars of the Norse world owe him a considerable debt of gratitude). I say "dying out", rather than "had died out", because Snorri wrote that Freyja alone of the gods still lived, which could mean that aspects of her cult were still practised in his own day. Among many other attributes, Freyja was the goddess of magic, witchcraft and divination (seidr) (Ellis Davidson 1964, p. 120). She could also change her shape, though she turned into a bird rather than a cat, and she could temporarily disguise her human lover Ottar as an animal (in his case, a boar) (Crossley-Holland, 1980, Hyndla's Poem).
Eirik's Saga, written in Iceland in the early 13th century, describes a volva (a seeress, prophetess, sorceress or witch), a human practitioner of seidr magic, who came to a farm in Greenland and foretold the future of everyone present (Eirik's Saga, ch.4). The volva wore a hood lined with white cat's fur, and gloves made of catskin with the white fur inside.
In the story of Thor's journey to Utgard, the giant and magician Utgard-Loki challenges Thor to lift a great grey cat from the floor of the hall. Thor, mightiest of the gods, tries with all his might to pick up the cat, but can only raise one of its feet a few inches from the floor. It is later revealed that the cat is in fact the World Serpent disguised by a magic spell (Crossley-Holland 1980). It may not be stretching a point too far to treat this story as another association of a cat with a practitioner of magic (though I won't insist on it).
So Norse tradition associates cats with Freyja, the goddess of seidr magic, with female human practitioners of magic, and possibly with a giant magician. The extant written sources date from the thirteenth century, contemporary with the other records from medieval Europe mentioned above, but there seems no reason not to accept that they may derive from earlier traditions.
Crossley-Holland, Kevin. The Norse Myths. Penguin, 1980, ISBN 0-14-006056-1.
Eirik's Saga, translated by Magnus Magnusson and Herman Palsson. Penguin Classics,
1965, ISBN 0-14-044154-9.
Ellis Davidson, HR. Gods and Myths of Northern Europe. Penguin, 1964, ISBN
0-14-020670-1.
Jones, M. The Secret Middle Ages. Sutton, 2002, ISBN 0-7509-2685-6.