This quest can be started as soon as the party reaches (read: crashes into) Fisherman’s Horizon. Exit Balamb Garden and head right until you find yourself on a walkway encircling a massive silo. Tower? Whatever it is, on the right-hand side of the walkway you’ll find an elevator leading down, which is where you need to go to meet the mayor, but first search for a very hard-to-see ladder on the left-hand side of the walkway.
Climb down to reach a lower walkway, then head left and up to find another ladder (still quite hard to see - grays and browns with low resolution, and all) then head left, climb up again and exit to another screen to find a fisherman sitting at the edge of a… crane? Whatever it is, he’d better hope he doesn’t hook anything too large, else he’s going for a swim. Talk to this Master Fisherman and answer as you will and he’ll give you a rare copy of Occult Fan III. Score.
Talk to him again and he’ll give you another errand, which you can complete as you explore Fisherman’s Horizon. He’s got a pupil at the docks (everything seems like a dock in this place) he wants you to talk to. Keep it in mind as you go about your business.
Return back right and climb up to the walkway above, then continue right and let the elevator operator - "Familiar Face" - take you down. Once he’s done babbling about Esthar and you ride down the elevator, head right a screen, then when you find yourself overlooking the solar dish continue right. Exit to the right again to find a Save Point and a Regen draw point, then exit to the right one more time.
You’ll find yourself on a screen with some tracks running just above the water. Ignore the inn to the upper left for now and instead use a dock to exit to the right again, then on the next screen head up to the end of another dock and talk to a boy - "Fisherkid" - on a boat. There are multiple skits you can view here involving the boy and the shopkeeper to the right, so just keep talking until the boy starts repeating himself, responding with Sort of, I saw him and I was sort of… impressed, in order.
Once the Master Fisherman’s quest is primed, continue right and talk to the old shopkeeper who nearly died due to what can only be described as impressive fishing incompetence. He runs the FH Junk Shop, so if you can craft any new weapons… well, here’s your first real chance in a while. Use a Shell draw point nearby, then exit back to the left.