Yes, gender applies to pronouns as well. It is a grammatical feature, not a biological.
Correct:
Ich habe meine Tasche gesucht, aber ich habe sie nicht gefunden.
Grammatical gender in English exists only in pronouns (he, she, it), and they are bound to the biological sexus (with some exceptions, like ships which are female too).
But in German each noun has a grammatical gender that sometimes even differs from the biological sexus (if there is a sexus).
And note that the gender is a property of the word, not of the thing named by the word!
Some examples for unanimated objects:
Das ist der Löffel, er liegt auf dem Tisch.
That's the spoon, it's on the table.
Das ist die Gabel, sie liegt auf dem Tisch.
That's the fork, it's on the table.
Das ist das Messer, es liegt auf dem Tisch.
That's the knife, it's on the table.
Persons:
- Sexus: male, Gender: masculine
Der Mann isst einen Apfel. Er trägt einen Hut.
The man eats an apple. He wears a hat.
- Sexus: female, Gender: feminine
Die Frau isst einen Apfel. Sie trägt einen Hut.
The woman eats an apple. She wears a hat.
- Sexus: unknown, Gender: neuter
Das Kind isst einen Apfel. Es trägt einen Hut.
The child eats an apple. He/she wears a hat.
In German children are treated as asexual beings. If you want to name the sexus of a child, you use Junge/Bub (boy) or Mädchen (girl) (for Mädchen see next example)
But sexus and gender do not always match:
- Sexus: female, Gender: neuter
Das Mädchen isst einen Apfel. Es trägt einen Hut.
The girl eats an apple. She wears a hat.
The word Mädchen is a diminutive, which you can see from its postfix -chen. And in German all diminutives are always neuter. This is a very strong rule, and it is one of the rare rules that have absolutely no exception. This rule is stronger than the matching between sexus and gender that normally exists in German for persons.
- Sexus: female, Gender: neuter
Das Weib isst einen Apfel. Es trägt einen Hut.
The woman eats an apple. She wears a hat.
The word Weib is an old word. Today you use Frau instead. But you still find it in the adjective weiblich which means female. (The word Weib is still in use, but it has changed its meaning. Today it has a meaning similar to vixen/shrew)
- Sexus: male, Gender: feminine
Die Tunte isst einen Apfel. Sie trägt eine Federboa.
The drag queen eats an apple. He wears a feather boa.
German is a living language, which means, that its rules are changing over the time. What I told you about Mädchen, Weib, Tunte and some more nouns where sexus and gender do not match, is still correct. But in the last 50 years, German native speakers began to use pronouns that don't match with the grammatical gender, but with the biological sexus, and since a few decades this is even considered to be correct too.
So today you are also allowed to say this:
Das Mädchen isst einen Apfel. Sie trägt einen Hut.
Das Weib isst einen Apfel. Sie trägt einen Hut.
Die Tunte isst einen Apfel. Er trägt eine Federboa.
But note that the matching of the pronoun with the grammatical gender still is correct too, so in this case, you can choose.
Examples for the same thing (a car) that has different names with different genders:
Der Wagen ist rostig. Er steht in der Garage.
The car is rusty. It is in the garage.
Die Karre ist rostig. Sie steht in der Garage.
The car is rusty. It is in the garage.
Das Auto ist rostig. Es steht in der Garage.
The car is rusty. It is in the garage.
As you can see, the gender is a property of the word, not of the thing. It is the very same rusty old limousine we are talking about here, but since we use different nouns with different genders, we also must change the pronoun.
(Der Wagen is often used for a bigger car, like a limousine. Die Karre is often used for an old and shabby car. Das Auto is the general translation of the car.)