The town of Mideel is the next official stop for continuing the story, but now that you have access to the Highwind there are a number of side quests that you can complete before hand - many of which involve revisiting towns that you have previously been to. Note that you may have already completed the first two if you have been following this guide all the way through.
Traveling to Wutai
A side quest which you may have already completed wherein Yuffie steals all of your Materia. This will be one of the last times in the game that you can complete this side quest.
The Wutai Pagoda
Also in Yuffie’s hometown of Wutai, this quest involves traveling to the Godo’s Pagoda at the back of town to obtain Yuffie’s final Limit Break, All Creation, and the Leviathan Summon Materia.
Returning to Nibelheim
Travel back to Nibelheim to obtain an Elemental Materia but only if you chose to “jam” on Tifa’s Piano during the flashback sequence. More information is available in the Kalm section of the walkthrough.
Returning to Cosmo Canyon
Travel to Cosmo Canyon to pickup a Full Cure Materia and a Guard Source.
Returning to Rocket Town
Travel back to Rocket Town to pick up the Fourth Bracelet and a Guard Source.
Chocobo Sage’s House
Traveling to the Chocobo Sage’s House to pick up the fourth and final Enemy Skill Materia.
Purchase some Mimett Greens from Choco Billy at the Chocobo Farm before you travel to Mideel.
The hot springs town
The town of Mideel is located on the southeastern continent and is identified by a red dot on the mini-map (which you can pull up at any time using the Select button). There is an Item Store near the entrance that sells the regular items including Potions, Hi-Potions, Phoenix Downs, Ethers, Hypers, Tranquilizers and Tents, but this item shop also sells an item called a Remedy. They are fairly expensive to purchase but they can cure nearly all status effects. Don’t purchase too many of them as the Ribbon accessories that you’ve recently acquired should be preventing you from being afflicted by many status affects already.
The Weapon Store is located up the stairs on the second level - the one with the girl in the blue dress standing out front. There are a number of great weapons and armor for sale including:
The lady that you see in each of the stores is the same woman with the same little white Chocobo. Speak to the Chocobo inside one of these stores and Tifa will offer to feed it the “Samolen Greens”. This is another typo in the game as Samolen Greens do not exist. Choose to give it some “Samolen Greens” and you will actually feed it the Mimett Greens and then choose to “Tickle behind his ears” and the Chocobo will give you the Contain Materia.
Contain Materia has some of the most powerful spells in the game once you get it levelled up. Tornado and Flare magic are on par with magic like Ultima and Comet. Very good Materia to equip on any of your more magic-focused characters.
Inspect the door at the back of the Weapon Store to confirm that it is locked. This needs to be done before you can proceed to the next steps. Go across the wooden bridge to the left side of the screen and just to the left of the man in purple and you will hear the ground make a noise as you walk over it. Examine the ground to find a “Beat-up Useless Old Key”.
Take the key back to the Weapon Store and attempt to use it on the door at the back. The man at the counter will ask Tifa what she is doing. You will have the option to either “Lie your butt off!” or “Tell them the truth!”. Choose to tell the store owner the truth. The store owner will then hand over a Curse Ring accessory.
Proceed to the north end of Mideel to continue with the story. Tifa will stop and talk to the dog before finding out that Cloud was found in Mideel and is in the clinic nearby. The story will continue for some time with Tifa deciding that she is going to stay behind with Cloud in Mideel.
You will regain control as Cid aboard the Highwind. Walk over to the Operation Room and speak to the man inside. Choose your party and spend some time equipping them with Materia, armor and weapons. Tifa’s Materia, if she had any equipped, will be back in your inventory. Speak to the (now LV6) pilot in training when you are ready to go.
Fly back down to Mideel before you go anywhere. There was one final house in Mideel that you never had the opportunity to explore near the area where Tifa found the dog and behind the two men that were overheard talking about Cloud. Enter the house to find a gigantic Elixir sitting on the bed.
You should also take this opportunity to purchase weapon upgrades for your characters if you need them. You have now likely been forced to make use of characters that were not normally in your primary party and you may not have been purchasing weapons for them along the way. Cid’s team will be exposed to some battles shortly so make sure that they are fully prepared to fight.