This article is from the Final-Fantasy and other Square Soft Games FAQ, by firstname.lastname@example.org (Nick Zitzmann) with numerous contributions by others.
You need Oxyale to get into the Sea Shrine. Oxyale can be obtained from
a spring in the Town of Gaia, but the fairy that lived at the spring
seems to be kidnapped.
A pirate in Gaia claims to have sold the fairy to a caravan. In the town
of Onrac, on the other side of the world, a person there mentions that
there was a caravan out in the desert and was holding a close-out deal.
Move to the desert and go to the spot with the trees in it. The caravan
is at this oasis, and they have a bottle on sale - for 50,000 GP.
Although it's expensive, you need to buy it.
Now, take the bottle to Gaia, and open the bottle. Head towards the
fairy spring, and the fairy will be back there. Talk to her to get some
Oxyale. You can now take the Oxyale back to Onrac and use the submarine
to reach the Sea Shrine.