You can travel to the Sunken Gelnika after you have obtained the Shinra Sub as a vehicle once you have completed the Underwater Reactor portion of the game on Disc 2.
That being said, the Sunken Gelnika contains some of the most powerful enemies in the game, so you may want to hold off and attempt going there later on in the game.
The Sunken Gelnika is a submerged transport airplane that crashed in the water and is located at the bottom of the ocean. It is entirely optional but it contains a wealth of great items that you should pick up.
Use the map above and the screenshot below to help you locate the Sunken Gelnika. The sunken submarine is located just south of Costa del Sol and just to the east of Gold Saucer.
An interesting note is that Emerald Weapon has a number of random locations that it can appear when you submerge the Shinra Sub. If you approach the Sunken Gelnika and find that Emerald Weapon is blocking the way just surface and then re-submerge your submarine and it will disappear.
There is no way to get around Emerald Weapon and into the Sunken Gelnika while it is guarding the way (there is, but it is safer if you do not attempt to get around it).
Touch the Sunken Gelnika to get inside the main hallway. There is a 
Save Point just up ahead after you climb down the ladder in the first room. Use it now and use it often as the enemies in the Sunken Gelnika can be quite deadly.
The chest to the left of the Save Point contains your first great new item which is a new sword for Cloud called 
Heaven’s Cloud. This sword has no paired Materia slots but it offers the highest amount of Attack so far at 93. Go through the door at the back wall leading north.
Cloud describes this room as some type of Research Establishment due to the Mako reactor found in the center. Follow the upper catwalk along to find a treasure chest that contains a 
Megalixir.
Backtrack along the catwalk and travel to the bottom right side of the screen to find a treasure chest that contains an 
Escort Guard. Escort Guard is similar to a Dragon Armlet; it doesn’t have the greatest Defense or Magic Defense stats, but it does nullify Lightning, Earth, Water and Poison based attacks. The other downside is that it can only be worn by men.
Travel down the ramp into the lower area of the Research Room. At the top left corner of the room is a hidden treasure chest that contains Yuffie’s Ultimate Weapon, the 
Conformer. Conformer has great Attack and Attack % stats, but like all Ultimate Weapons, it does not provide any Materia growth.
Finally, towards the upper right section of the room on the bottom floor is a piece of Materia (partially hidden behind the Megalixir treasure chest) called 
Double Cut Materia.
This Materia allows a character to attack twice in succession and is one of the strongest pieces of Materia in the game, particularly for characters that are focused on regular attacks rather than magic-based attacks.
This weapon should be equipped to Cloud straight away, especially in light of his newly acquired Heaven’s Cloud sword. Travel back to the Save Point once you have obtained all of these items.
Save your game one more time in preparation for an upcoming boss fight and then travel through the door on the left side of the screen.
Reno and Rude can be seen just up ahead as soon as you enter the next hallway. Make sure that you equip both of the 
Ribbon accessories that you have on your party members to prevent the Confuse status effect (caused by Reno’s Neo Turk Light ability) from making the fight more difficult.
Note that this battle will only take place if you have not already traveled to Midgar at the end of Disc 2.
The most important thing to do during this fight is to steal from both Reno and Rude using your Steal Materia. You can steal a Touph Ring from Reno and a Ziedrich from Rude - both items that are difficult to obtain and are highly useful.
The remainder of the fight is fairly straightforward. Use Big Guard from your Enemy Skill Materia early on in the fight and lay into both Reno and Rude with your most powerful attacks.
HP: 15,000 (Rude) + 20,000 (Reno)
Reward: Elixir
Travel down the hallway and through the doorway after the battle has concluded.
The first treasure chest directly in front of the entrance to the Cargo Room contains another Megalixir. Stay on the upper platform and follow it around to find another treasure chest that contains a 
Spirit Lance for Cid.
On the bottom floor are two treasure chests close to the screen - one contains an 
Outsider weapon for Vincent and the second contains Highwind, Cid’s Level 4 Limit Break.
Gale Warning
You will receive the Gale Warning Trophy once you teach Cid his Level 4 Limit Break, Highwind, using the Highwind item that you pick up here in the Sunken Gelnika.
Check out the Learning New Limit Breaks section for more information on how to teach your characters their strongest Limit Breaks.
The last item you need to pickup is a small piece of red summon Materia lying in amid the machine wreckage. Use the screenshot below to help you locate it.
This is 
Hades Materia - a mediocre summon Materia in and of itself, however it is extremely powerful when paired with 
Added Effect Materia as it can potentially cause Poison, Confuse, Sleep, Silence, Mini or Frog on enemies that you attack.
You are now done with exploring the Sunken Gelnika and obtaining the items and rewards, however the Sunken Gelnika is a great place to level up your characters and to level up your Materia. Just equip weapons with Double or Triple Materia growth and level away.
