The Catgirl is sterotypically female, perhaps because of the Feline Female association, or perhaps because Most Writers Are Male. Many fans appreciate catgirls because they’re cute and they suggest softness, cuddliness, aloofness and hidden claws. The combination of feline and female seems to resonate strongly in the collective muse and shows up in many forms, ranging from the "10,000 horsepower innocent" cyborg Nuku-Nuku (from All Purpose Cultural Cat Girl Nuku Nuku) all the way up to the devastatingly sexy criminals such as Ana and Una Puma from Dominion Tank Police and Catwoman.
Expect a Western feline-themed character to be portrayed as especially sexy and especially dangerous, with Femme Fatalons and agility second only to Spider-Man. The Cat Suit is usually the outfit of choice. Cute Little Fangs are sometimes present but seldom used in a cute manner. Claws, whether natural or in the form of clawed gloves, tend to be particularly popular.
The Japanese (or at least manga and anime creators and fans) seem to have a particular fascination with catgirls, which they call Nekomimi, which translates to literally "cat-eared". They are found in genres as widely varied as High Fantasy (Merle and others in Vision of Escaflowne), light comedy and Cyberpunk, proving that they are not a setting-specific feature, but a general type that can be inserted into just about anything. The Catgirl motiff in Japan seems to have roots in ancient myth with a Nekomata, but the first true catgirl (and thus the trope) appears to have been created by Osamu Tezuka in the 1950s.
In Japan the Catgirl is closely associated with Moe. It is noteworthy that the most common method of drawing anime characters, particularly females, tends to give them catlike features (large eyes, a small mouth and a skull shaped much like that of a young human child) - and that cats are extremely anthropomorphic for non-primates in the first place. Given this, the Catgirl is possibly nothing more than the logical conclusion of this. Anime Catgirls usually have Cute Little Fangs and a tendency to use a Cat Smile when happy. Female Catgirls often have a Genki Girl personality. Anime characters which are not actually catgirls often show up as catgirls in the fantasies of other characters. Collars often make a prominent appearance in such cases. In a less suggestive context, playful female characters often have catgirl avatars in Cyberspace sequences.
However, it is worth noting that this trope is primarly about appearance, not gender, and that male examples of characters with real or fake cat ears are by no means unheard of. In the early decades of anime there were few dog and cat-boy characters because there was largely no place for them in anime. They had no role to serve and no audience to appeal to. As of the 2000s and the evolving characteristics of anime and anime viewers, there became more of a demand for catboys, particularly in media targeted at a female audience, hence more of them have begun appearing. See here for more information. They tend to be either Keets or bad boys, and are actually more likely to wear collars than their female counterparts - especially in Fan Art.