Mr.Kitty - SouthPark wikia mentions the gender as male. This is the gender potrayed throughout the series, with the exception of a single episode.
The only episode where Mr.Kitty is depicted as a female is Cat Orgy.
Mr. Kitty would later have prominent role in "Cat Orgy", in which his/her gender has shifted back towards female and he/she is in heat. After attempting to have sex throughout the episode, Mr. Kitty assembles a massive group of male cats to come home with her. She then proceeds to get all the cat's high on catnip (which they snort like cocaine) and all the male cats proceed to take turns having sex with Mr. Kitty. Cartman and his babysitter Shelly Marsh were, needless to say, horrified.
Even Wikipedia mentions this -
Although Mr. Kitty is indicated to be female in "Cat Orgy", there are examples of where he's portrayed as a male; in the season 12 episode "Major Boobage", the children experiment with Mr. Kitty's urine after learning that the urine of male cats can cause intoxication, indicating that Mr. Kitty is actually male.