There are 6 different girlfriends, each giving CJ a different perk upon 100% dating progress. You can see a detailed overview here, but summing up, they are:
- Denise Robinson
- Millie Perkins
- Katie Zahn: At the north east corner of the golf course in San Fierro, katie is practicing Martial arts near some bushes. You should be able to see her easily from the road.
- Barbara Schternvart: Find the sheriffs building in El Quebrados, The desert. She'll be outside talking to someone.
- Michelle Cannes: Enter the driving school and she can be found inside talking to someone.
- Helena Wankstein: Go to the small town of blueberry and find ammunation. If she is there at that time, you will here her firing a gun at a target range beside ammunation up some steps.
You meet Denise and Millie on required missions (Burning Desire and Key to her heart, respectively). The others you have to find.