Willow cats refer to (at least) two different species of catfish. This can be confusing, but matters are simplified by the fact that one is a good eating fish, and the other is used only as bait. Both senses of the term are in common use in the American South, and the former is also used in Texas and on up into Ohio.
If you're looking for a fish to eat, Willow Cat is one of the many common names for the large Channel Catfish. Webster believes that it is specifically a member of the species Ictalurus anguilla, although in common usage it is probably more frequently used to refer to the Ictalurus punctatus. Other common names include fiddler, spotted cat, speckled cat, and chucklehead (this last is also used, outside of the American South, to refer to the Copper rockfish).
How this fish came to be known as the Willow cat is a bit of a mystery, as they prefer to hang out in fast moving channels. It is possible that the name first applied to other catfish, such as the Flathead, that prefer to hang out in the root of trees, and later spread to the more popular and well-known Channel Catfish.
It is also quite common, especially in Mississippi and Missouri, to refer to a type of bait fish as a Willow Cat. These are young members of family Ictaluridae, commonly known as the Madtom, and specifically those of the Tadpole Madtom (Noturus gyrinus) species. They are quite tough, and Walleyes are the only fish that like them; however, they are reputedly very effective at hooking Walleyes. Many species also have poisonous spines on their back, giving the equivalent of a bee sting to anyone who is not careful when baiting their hook. These are also sometimes known as Tomcats.
It's no mystery how these fish got their name; they prefer to hang out among the rocks, in nooks and crannies, and yes, in willow roots.