After you get the ultimate key from the old lady and the dog flies away..

Use the ship to go under the checkpoint near Alexandria. There is a cave called pirates cove. Go in the locked door and Red will come along and go it. Once you reach the end of the cave (this may take a few tries for anyone under level 33) you will fight captain Crow. Trust me DON'T waste your magic in the cave. You WILL need it on him. When you beat him you will receive the sea chart. Then you must find your way to the island surrounded by mountains. Once you reach Empychhu(the town on the island) talk to everyone. Then find Empyrea's roost and follows Empyrea's shadow until you reach the dark eye.(you MUST follow the shadow or you CAN'T find the dark eye) Then make your way to dark Empychhu. Talk to everyone then make your way to Empyrea's roost (again). Once there you must fight and defeat Empyrea. (level 35 or bove recomended)...And that answers your question basicly.

You get the sea chart in Pirate's Cove. If you look on the world map, in the first continent you started the game at, there is a river that runs all the way through it. Go through this river, and you will sail under a bridge close to Alexandria. There is a cave under this bridge, go through it. You have to defeat Captain Crow in it, I recommend being on level 32. You will get the sea chart. Use it to get to a new continent and eventually find Empyrea.

To get the seachart you must head by sea to that southern checkpoint that came after Farebury. Use your map and you'll notice a river seperates those two continents. Underneath the bridge there is a cave, steer your boat in to it. Go through the barred gate to activate a scene with red. The rest is pretty much straight forward.

Under the bride where you cross to alexandria you can find the pirates cove. It's at the end.