HandyNotes: Secret Fish
Initially you'll see icons only in Mechagon, showing valid locations to fish up the quest fish there. Give them all to Danielle Anglers and you'll earn the Secret Fish Goggles.
Now icons will appear all over the world. Just look at the map of Azeroth and follow the fishing hooks. There'll only be icons on specific zone maps if there are precise locations you need to collect the secret fish in. Make sure to use your goggles.
There are other fish which will be found anywhere in the world, and two which are day/night specific. These have no icons.
If you need more details, check out this guide.
Note that this requires HandyNotes, so go install it as well.