The parts location are only appearing when the Scuba-diving activity is being triggered, not anytime you're going into the ocean.
The difference between the two is that you have to get inside of a Dinghy or a Submersible. Then as soon as you exit one of those you'll be equipped with a scuba tank and breathing apparatus. At this point you'll start to see the closest piece on your map represented by green circles on your map. The Trackify app won't be launched since this one is only used for the nuclear wastes and some specific story-related missions.
Sources: Submarine Pieces - Scuba Diving
Edit: Oh yeah, and of course you have to buy the Sonar Collections Dock first with Michael ;)
Edit2: I think it is still possible to collect the parts without being in "Scuba diving mode" though. You will just see them on your mini-map instead of the full one, this can be useful if you're passing by a part that is not too deep (as for the ones in the city channel) but I would recommend getting the scuba gear for the full run.
Edit3: If you're wondering about where to find the vehicle: Dinghy - Submersible