Actually it's the gender of the person/animal that usually determines the grammatical gender of the noun: the pronoun always agrees with the grammatical gender of the noun, but that gender is almost always identical to the natural gender.
For instance, if you're referring to a she-cat or a cat of unspecified gender, you use кошка (feminine), but if you know the cat is a he, you should use кот (masculine):
Где мой кот? Я его не вижу. is also a correct translation.
How regularly do Russians distinguish male and female cats? Because I put him, assuming that it was like German where, although there is a word for a male cat, it is not usually distinguished from the usual feminine form, and most people do not refer to their pets as it (and my cat happens to be male so that's what I thought of first).