You will probably find your first oyster during The Da Nang Thang. There are fifty to collect after that.
Collecting all 50 oysters results in increased lung capacity and sex appeal. That's right, the reward for all that swimming is that you are able to swim longer.
The increased Sex Appeal allows you to start dating any girlfriend regardless of her preferences for muscle/fat, and that she will invite you for Coffee right after first date.
- SAM Oyster location map
- Oyster map by 708145 with full map and links to CJ's point of view and map locations for each oyster.
- Directional Oyster Guide (text) by YuGiOhFm2002 & YuGiOhAngel
The best way to acquire the 50 Oysters is using the "Los Sepulcros" or "Reuniting the Families" tricks which allow you to navigate the entire map without being attacked by the police, even if you get five stars.
You could use a boat to collect the San Fierro/Angel Pine/Red County oysters, or navigate to Sherman Dam. At the southwest of the Dam there is a Seasparrow you can use to collect the Tierra Robada/Las Venturas oysters, you will be attacked by missiles if you pick it, but it's still the fastest way to acquire the oysters