"For the cat is cryptic, and close to strange things which men cannot see. He is the soul of antique Aegyptus, and bearer of tales from forgotten cities in Meroe and Ophir. He is the kin of the jungle’s lords, and heir to the secrets of hoary and sinister Africa. The Sphinx is his cousin, and he speaks her language; but he is more ancient than the Sphinx, and remembers that which she hath forgotten."
Yoruichi from Bleach often opts to wear the guise of a black cat.
Haruhi Suzumiya has Shamisen, the calico cat. He (male calico cats being extremely rare) originally started as an ordinary cat, but was briefly given the ability of speech. This was because Haruhi believes witches need magical cats, and this belief altered reality and made Shamisen magical. She never finds out that Shamisen could talk, but was originally a little disappointed that he wasn't a black cat.
In Sailor Moon, the characters find out they are Sailor Soldiers/Senshi/Scouts with magic powers because two talking cats with crescent moons on their foreheads, Artemis and Luna, appear to inform them and guide them as they try to save the world. They can even make magical items appear by doing backflips.
Kuroneko-Sama from the anime Trigun, the black cat randomly appears across the desert planet Gunsmoke where our hero's show up. Fan Wank is that Kuroneko-Sama is God.
It doesn't help Soul or Maka that Blair's human form happens to have the iconic pointy hat and flowing robe (though Blair's robe is only flowy in the sleeves. The rest resembles are very short miniskirt with tank-top.)
Happy, Charle, Pantherlily, and all the Exceed from Fairy Tail apply.
Gatomon from Digimon possessed the attack "cats eye hypnotism" and she was rather mystic in nature
In the manga Leviathan, cats are mentioned in passing to be able to see spirits.
The cats in ARIA, especially the Mars variety. And then there's Cait Sith.
The cats in Windy Tales seem to have a natural talent for manipulating wind.
Cats in the Lyrical Nanoha verse are one of the two animals we've seen used as familiars, and are typically more magically oriented than the more physical oriented wolf familiars. In fact, all of the known cat familiars in the franchise have served as magic tutors, with Rynith teaching Fate, and the Lieze twins teaching Chrono.
Kirara of InuYasha is a "nekomata", a cat that has lived for a very long time and has developed a split tail and magic powers. In Kirara's case, she can grow to a giant size (large and strong enough to easily carry three full-grown people), fly, and is often Wreathed in Flames in that form. She is also notably more intelligent than your average animal, though not quite sapient.
Coraline has a cat that can move between the real world and the Other Mother's world. At the end of the movie, he is shown vanishing into thin air.
The Last Unicorn has a talking cat that gives Molly the hint they need to save Amalthea and the unicorns. It was also the only creature that could see through the spell Schmendrick put on the unicorn. Bonus points for being the only cat on this list with an Eyepatch of Power.
Films — Live-Action
Hocus Pocus: Binx, a teenager who was transformed into a black cat by a trio of vengeful witches. He has the ability to speak, and he is effectively immortal. No, he doesn't have nine lives, he just can't die.
At one point in The Mummy, a normal cat that Evelyn brought with her on the adventure is able to ward off Imhotep because "cats are the guardians of the underworld". This is demonstrated once, and exploited only a single time following that, because Imhotep completes his regeneration soon after and becomes immune to whatever the cat would supposedly have done to him. It's still a Crowning Moment of Awesome, as Cleo gets in on the act.
And in H. P. Lovecraft's novel The Dream Quest Of Unknown Kadath, the cats of the Dreamlands can travel to the Moon on their own power and have a secret language. They worship Bast and aid the hero in his quest. The only thing the Earth-cats fear are the cats from Saturn, who are even more powerful than they, but are in league with the Eldritch Abominations.
Tamora Pierce's The Song of the Lioness series features a mysterious black cat (Faithful) who makes an appearance in the Beka Cooper Trilogy as Pounce, the cat constellation who has come to Beka for undivulged reasons.
Un Lun Dun, by China Miéville, subverts this by making cats the most stupid and least magical of all animals. Dogs, foxes, various birds, and even fish are shown to be sapient and able to cross the boundaries between worlds, but cats are too concerned with looking cool to learn anything of value.
A black cat in Neil Gaiman's Coraline can talk in the Other Mother's universe, and acts as a sort of Mentor towards the heroine.
Neil Gaiman's short story The Price is about an otherwise ordinary black cat who, on a daily basis, protects the narrator's home from a demonic entity. The black cat gets more and more beat up with every fight, and when he fails to fight the demon, the narrator's household is afflicted by numerous misfortunes.
In L Loyd Alexander's, Time Cat, all cats have the ability to travel to any place they choose, in any point of time they choose. This is said to be the reason why they can vanish mysteriously in small rooms.
Discworld's Death is very fond of cats and gives them all nine lives. That said, the only cat who is really magical is Maurice, from The Amazing Maurice and His Educated Rodents. He gained sapience and speech by eating a rat who had, in turn, also eaten some magical garbage.
Greebo, the epitome of Cats Are Mean, has the ability to turn into a human (a muscular, agile, and very much naked human male) in times of danger ever since the witches put a spell on him.
Nakata from Kafka on the Shore has the ability to talk to cats. Siamese cats are said to be very easy to communicate with.
Jonnie Walker, another character from the same book, kills cats and uses their souls to make a magic flute.
Cats in the Young Wizards universe are the only Earth species which can naturally see the string structures out of which wizardly Cool Gates are made, so the maintenance teams for Cool Gate clusters are all made of cat wizards. Also, even non-wizard cats can sometimes spontaneously walk through walls.
In the Polish short story "Because the cat" a company designs computer systems that allow children to learn at a fantastic rate, creating associations after a single exposure to a given situation. Unfortunately, it goes bankrupt as several of the devices break down - the system responsible for recognising just what is the right association suffers a self-inflicted Logic Bomb, as it tries to make sense of the reality around it. One of the children was damaged more than others - the boy has a pet cat and the faulty system has built his entire logic around the animal, attributing all that is happening to its behaviour. The characters consider the child a hopeless case and consider euthanizing him - until he gets bored and uses the cat to Reality Warp himself out of the hospital.
In Diana Wynne Jones's Dark Lord of Derkholm, Dirk's cats, which he bred to be invisible, are also inexplicably unable to be trapped for long, they always find their way out, even from magical barriers.
The cat from Stephen King's film "Cat's Eye" definitely applies here
In Garth Nix's Old Kingdom trilogy, there is Mogget, the sarcastic, fish-demanding, white feline servant of the Abhorsens who is actually Yrael, one of the Nine Bright Shiners, and a free magic creature, bound by a ring. Kerrigor, a powerful necromancer, is bound along with Mogget by the same ring and becomes a sleeping black cat.
Robert Asprin lampshaded this in one of the Myth Adventures books: "Cats and computers can work through dimensions."
Subverted in Mercedes Lackey's Diana Tregarde story "Arcanum 101." When Di is observing the house of someone she believes may be involved in black magic, she sees a cat wander past the house with no reaction... and thinks to herself that this doesn't mean anything because, superstitions notwithstanding, cats are too self-absorbed to notice magic that isn't affecting them directly.
Mrs. Norris of Harry Potter. She seems to have some kind of psychic link to her master (which is odd because he himself has no magic). Or him showing up a few minutes after she catches children being mischievous is a complete coincidence.
Hermione's cat Crookshanks is part normal cat, part magical creature called a Kneazle. As a result he is able to see through Sirius's Animagus form and is much more intelligent than a regular cat.
The Ghatti's Tale books feature cats with psychic powers who bond with humans. Humans partnered with cats act as arbiters because of the felines' ability to "mindwalk." The Ghatti, however, are noted as being natives of their planet and distinct from "normal" Earth-origin cats despite sharing many similarities.
Warrior Cats. When cats die, they go to StarClan, where they can enter living cats' dreams, influence real-world events by creating omens, and even enter the physical world from time to time.
In the Toby Daye series. all cats are loyal to the local King of Cats, aware of magic, and much smarter than they let on. And this is the ordinary non-magical cats. There are also the Cait Sith, who are cat fae and outside the normal fae laws for being cats.
In Saki's short story "Tobermory", Tobermory magically becomes able to talk, and horrifies a group of party guests by tattling on all the sins that he's been spying on over the years.
Robert Westall's fiction was often built on this trope. The Cats of Seroster is all about magical cats and short stories, The Creatures In The House and Fred, Alice and Aunty Lou involve cats having powers to perceive things beyond what humans can.
In Andrzej Sapkowski's The Witcher novels cats are mentioned to be the only species of animal apart from dragons to actively seek out magical Intersections which radiate Power, and rest in them, although no-one knows what they do with the Power they gather by doing so.
In the Thursday Next Series, the Cheshire Cat is the Librarian of the Great Library of all books ever written and not written. He can appear anywhere, in any world, fictional or real. He also has the ability to say how many and who is reading any of his books at any time. He is watching you!
In an episode of Charmed a witch's Familiar turned on her and became a Warlock. Sorta the reverse of what happened on Sabrina with Salem.
Of course, the sisters have their own feline familiar. She became a human as a reward for her service to the forces of good.
Myth and Legend
Ancient Egyptians worshiped the goddess Bast, who was cat-headed and held cats to be sacred. At some points in ancient Egypt, harming cats carried the death penalty.
In Japan cats are said to give good fortune, which is why you see welcome/lucky/beckoning cats (white ceramic cats with a gold coin and one raised paw) in some establishments. The lower paw (which is often holding a coin) is to protect money, and the raised paw draws money in.
A black cat crossing your path is said to be bad luck in most of continental Western Europe
On the British Isles Black Cats have better press for some reason and are usually associated with good luck
A woman with a cat, especially a black one, will have more suitors.
In Scotland, the arrival of a strange black cat to a house is supposed to signal good fortune for everyone in the household.
The urban legend that shelters won't allow black cats to be adopted around Halloween in case they're killed and tortured ritualistically (the former is true, the latter is unsubstantiated).
Ship's cats (especially black ones) were said to be lucky by sailors, although pirates often believed that a ship which had a black cat walk on then off was doomed to sink. The ascribed good luck, at least, is probably more attributable to the fact that ships traditionally have rat problems than any magic, however.
Many modern Pagans, including Wiccans, hold cats in high esteem. In Wiccan rituals, it is believed a cat can walk through a magic circle without breaking it, since cats can walk through spiritual/magical borders. Another animal, like say a dog, would break the circle and thus dispel any magic.
Cats are believed in some cultures and traditions to be able to see spirits and ghosts.
Bast is an Elder God and the basis for the Egyptian pantheon's version.
Dreamlands supplement. In the Dreamlands, cats can travel to the Moon on their own power and have a secret language. They worship Bast.
Aside from from the entire world being implied to exist in some in-between realm, Mistoffelees from Cats, who uses his magical powers to save Old Deuteronomy from Macavity. There are also a few other cats who are hinted to have magical powers, such as Macavity himself, and Coricopat and Tantomile.
Felineko of Solatorobo are stated to have a gift with magic, possessing both interest and talent.
Dragon Age: Origins – Awakening: Ser Pounce-A-Lot, a cat that can be given as a gift to Anders and when used as an item in combat can revive fallen party members.
Both Mew and Mewtwo from Pokémon are capable of powerful psychic attacks. Mewtwo itself is also capable of speaking telepathically to humans. Both are cat-like creatures with Mew resembling some sort of pink fetus-like kitten and Mewtwo resembling a mutant humanoid feline.
Espeon is loosely based off of a Nekomata, a two-tailed cat of Japanese folklore that had psychic powers.
Landorus's "Therian Forme" is that of a feline-like creature.
Generation VI introduces Espurr and it's evolution, Meowstic.
Spark from Dominic Deegan is a cat who can talk, which causes some people to believe that he's possessed.
Rose, who is arguably the most magical of the four kids in Homestuck, prototyped her dead cat Jasper to her kernelsprite, and also made a genetic sequence using the letters MEOW (instead of the typical GCAT) which can be spliced with other DNA to create godlike entities.
After the universe is rebooted, we meet an actual GCat, likely made with a BARK sequence. The G, of course, stands for God, since, as a First Guardian, GodCat is pretty much omnipotent.
Poe from Neko the Kitty Comics can speak English, levitate, and has minor telekinetic powers. Explained in this strip: Poe was accidentally sucked into an ethereal conduit when the witch Julia was attempting to summon a lesser demons. Demons are unable to possess cats, so when they manifested together in the summoning circle the demon died, leaving Poe with his magical abilities.
The two specialists in Spare Keys For Strange Doors own a cat (called "Fat Cat") who can see the ghost of Andrew Cole in the storyline "After Death Hang-Ups". And be aggrieved that he can't sit in Andrew's lap.
Basement Cat, and Ceiling Cat!
To elaborate: Lol Cats, over the years, have accrued a small mythology. Ceiling Cat, based off a picture of a cat that was stuck in between the walls of an apartment that was rescued when a hole was cut in the ceiling, is considered the God of Lolcats. Basement Cat is just any random black cat, and is considered the Devil. There are others, such as Longcat, who can stretch to any length and is sometimes depicted in an epic battle with its Evil Twin, Tacgnol.
In the second season of W.I.T.C.H. Lillian's cat Napoleon becomes her familiar after her Heart of Earth powers manifest, the most prominent effect on him being his ability to speak after she wishes they could a have a conversation together. Before this he was just a regular cat given to Cornelia by Will, so he wasn't inherently magical. Later, he gets the ability to change into a seven-foot tall cat monster after becoming a Regent of Earth.