The connection between black cats and Halloween is complicated and frequently unclear. There are many claims made about connections, but many of them lack historical backing.
Witch FamiliarDuring the European witch-craze, witches were widely believed to keep familiars, which were malevolent spirits or demons that disguised themselves in the shape of animals and often fed off the witch's blood. Cats were certainly considered potential familiars. After all, everyone had them to help control vermin population. But there were plenty of other animal familiars as well, including dogs, ferrets, birds, spiders, goats, toads, and hares, all of which could easily be found in the vicinity of most suspected witches.
Nature of CatsCats do have some qualities that can make them creepy to suspicious people. They are relatively intelligent, but they are also not terribly social with humans, unlike dogs. They're harder to train and more often live on their own. They are naturally nocturnal, and humans naturally view nighttime as a time of danger before the invention of electric light because humans have terrible night vision.
Papal Bull Against CatsTwo papal bulls are sometimes pointed to as evidence of official persecution of cats. The first is the Summis desiderantes affectibus decreed in 1484 by Innocent VIII. This is the document commonly used to mark the beginning of the European witch-craze. However, while the document accepts the reality of witchcraft and threatens lay people with excommunication if they do not cooperate with Inquisition investigations on the matter, it doesn't mention cats.
The second document is another papal bull, Vox in Rama, theoretically released by Gregory IX around 1232. The problem with this document is there's doubt as to whether it actually existed. The first reference to it is relatively modern, a good 500 years after the reign of Gregory IX.
The Color BlackIn Christian cultures, white is generally a symbol of goodness and purity, and black is a symbol of danger, corruption and evil. Any sort of black animal therefore could be more suspect than animals of other colors.
Natural Superstitions about Black CatsMany urban legends state that Europeans have a long history of folklore vilifying black cats. In fact, there's a wide variety of folklore about black cats, of which some are positive and some are negative.
Cat Worship in EgyptIt's certainly true that cats were held in extremely high esteem in Egypt. However, there is absolutely no reason to think that things that happened thousands of miles away would color beliefs in northern Europe hundreds or thousands of years later. Some claim that the Church vilified cats to counteract their divine status in Egypt, but there's no evidence of this, and it really reaches beyond common sense.
This belief presumes that large numbers of people in Europe had every aspect of their lives ruled by the Church, which is simply not true. There were all sorts of folklore that was not only separate from Christianity, but even ran counter to it.
Modern TraditionRegardless of how black cats became associated with Halloween, the mere fact that it has become associated with Halloween is a reason for it to remain so. Seeing black cat decorations at Halloween reinforces the connection between black cats and Halloween.
As a comparison, consider the green-skinned witch often used in Halloween decorations. The first known depiction of a green-skinned witch was in The Wizard of Oz, a source that has absolutely nothing to do with Halloween. But, for whatever reason, we started making witches green in Halloween ornaments, and now it’s an accepted part of Halloween.