Wutai

Wutai is on the western most island on the world map. You can go to it, immediately after you get the Tiny Bronco from Cid. It is actually recommended that you go there right after, as you can gain some great items. If you go later, the luster of the items you get are not all that great anymore.
Land the Bronco on the shore, and make your way north up the path. Right before you reach the top, Yuffie will try and stop you.

Things seem a little fishy with our famous ninja, but before you can question anything Shinra attacks you. When the battle ensues, you will notice that you only have your attack and item commands available. This would be a great time to utilize any of the magical items you have stored in your inventory. Get through the fight as quickly as possible. Afterwards, you will realize that Yuffie has made off with all of your Materia. Now you have no other choice, but to go to her village in the north.

When you arrive at Wutai, you will catch a glimpse of Mrs Yuffie, before she runs off again. Well, at least you know she is here. You need to begin your search for her. Speak to everyone in town, and you will eventually be directed to the far side of town. When you get there, head into the home on the right.
You soon find this to be the home of Lord Godo. You will find him sleeping in his room. Continue talking to him, until he gets up. At this point, Yuffie will enter the room, and a massive argument will ensue. Apparently Yuffie is the daighter of the lord of Wutai, and niether is too happy with the way the other is handling things. Godo will chase Yuffie out, and there you are back at square 1.

*Note* Before leaving the house to look for Yuffie, there are a couple of somewhat hidden rooms to get to. The first is in the room next to Godo. Here you will find the Hairpin weapon for Red XIII. In the guest room behind the curtain, you will find the Magic Shuriken for Yuffie. (Though after taking your Materia, I bet you are really thinking about selling it off instead.)
Head back to the main part of Wutai. Enter the Turtles Paradise, and initaite a conversation with the Turks. You are ready for action of course, but you find that the Turks are actually on vacation...what a relief.
Head back outside, and go to the boy in front of the item shop. He will tell you he heard noises inside the shop. Head inside, and you will see a chest that is ripe for the taking. Open it up for an MP Absorb Materia. Just as you are about to place it somewhere safe, Yuffie drops out of nowhere and steals it too. Bet you are really wishing you had never found her now huh?
Head back outside, and make your way to the house by the entrance of town. When you go inside, the owners will make mention of more strangers...more strangers huh? Check behind the divider to find Yuffie hiding. She will race out of the house, before you get a chance to grab her.
Now head back over towards the Turtle Paradise. Notice the shaking jar by the door? As you approach it, Everyone will split up, and block the exits. Now hit it a few times, and a ninja should pop right out. Finally you have caught Yuffie! She will lead you back to ehr home to get your Materia.

Inside her home, Yuffie will begin to tell a bit of the history of Wutai, and why she is seeking Materia. But before she can get too far into her story, Cloud cuts her off, and demands the Materia. (And he just cold as all get?) She will then lead you into her basement.
Before entering the small room, read the final Turtle Paradise Flyer on the right side of the doorway. Now go in, and she will tell you to pull the left lever for your Materia. It doesn't matter which lever you pull, you will quickly learn that Yuffie has pulled a fast one on you! Free your companions, and go out to find her once again.
Head back to the far end of town. You will notice that the gate on the left side by the bell is now open. Go to the bell, and ring it. This will open a secret door. Go inside, and you will find Yuffie, and someone you probably thought you would never see again.

Don Corneo has apparently slipped away from Shinra, and is still looking for a bride. This time he has captured not only Yuffie, but Elana of the Turks as well. As you lend chase into the next room, Shinra soldiers will enter from the other side. Corneo slips by both of you, leaving you to take care of the troops. Finish them off, and follow Corneo out of the house.
Outside you will run into Reno and Rude. They will agree not to fight you, since you are both missing a person in your party. They will give you a hint on where to go next. So get going already!
If you have the extra Gil, make a stop at the item shop and stock up on Hi-Potions and Fire Veils. Now head over to the Da-Chao statues.
You will run into Reno and Rude again, and they will run off in different directions. You will want to go up the hill, and take your first right. Now run around the back of the Da-Chao head, and into the next screen.Here, you will see Rude enter a cave. Head in after him. This is the Da-Chao cave. Outside of the entrance, it is completely filled with flames. Open the only chest available, to get Cid's Dragoon Lance, and head back out. Now follow the path down, and you will find who you are looking for. Corneo has managed to not only get all the way here, but he has strapped Yuffie and Elana to the eyes of the Da-Chao. Don will try pleading with you about his troubles, but you will stop him fast. (What is it with everyone wanting to spill their hearts out on you???) He will then introduce a new toy for you to play with. Get ready for one tough cookie.

Boss Fight: Rapps

Without your Materia, this can be a brutal fight. You want to have a lot of Hi-Potions and Phoenix Downs to survive. Rapps has several normal attacks that hit for 200-400 HP damage. As bad as these are, his Aero 3 attack will drain a whopping 1500+ HP. This will take out a party member easily. If you have any items that set up defense and magical defense, use them right away. Then hit him with any magic items that cast level 2 and 3 of the elemental spells. Make sure to keep everyone healed at all times. If you must, have only one attack, while the others serve as medics. Another method is to place Barret in your party. Set his Limits to level one, and make sure he can use them right off the bat. Hit rapps with Mind Blow one time, and he will lose the ability to use Aero 3. This will certainly make the battle a whole lot easier. Just keep at him, and eventually he will succumb to defeat. For your hard earned victory, you will get a Peace Ring.

After the battle, the Turks will step in and finish Corneo off. They will then get orders to seek out Cloud and company. Before you get into a fight again, they decide they are on vacation...basically they are letting you go for helping out. Yuffie will then return with you to her home, and hand back over the Materia she took from you. You will then appear outside of town. Your materia will be somewhat out of order, so make sure it is set up right. She even begins trying to warm up to you again. As everyone leaves, she runs over, and gets the MP Absorb Materia for you.
Before you decide to head back to the Bronco and continue the journey, there is more things to do in Wutai first.

The Pagoda of trials

After you get Yuffie back, place her in your party. It is time to see how well she fairs againts the Gods of Wutai.
First get Yuffie set up. Make sure to give her the best armor and weapon you have. The Magic Shuriken you found in Godo's home will do fine, or you can drop some Gil for the one sold in the Weapon Shop. Yea, the weapon seller is a lot nicer now, and will sell his goods to you.
If you have already gone to the Temple of the Ancients, give Yuffie the Ribbon accessory. If you have not ventured there, you will need a Jem Ring for one of the fights ahead. There are others, but they are not as important.
Set Up:
Place the combination Added Effect + Poison into Yuffie's weapon. All of the bosses ahead can be poisoned. This can give you an upper hand in any given fight.
Give Yuffie a Restore materia, as well as an Enemy Skill with Big Guard. If you have the ability to, give her the Long Range and Counter Attack materia as well. If you have a Enemy Skill without Trine, be sure to set it in somewhere. You can then fill the rest of the slots with what you need. Choco-Mog is a good summon, as well as Bahamut if you have it. Make sure you save in town, and then head to the Pagoda in the end of town. (It is the tower by Godo's home.)
Yuffie will now have to face five of the Pagoda Gods. There is one on each floor, and you ahve the ability to go save and heal between fights. This is good, since Yuffie might not be strong enough to make it through the final boss. If this is the case, take her out around Wutai and level her up.

Boss Fight: Gorki

For this fight, you might want to place the Elemental + Gravity combo to her Armor. this will help reduce Gorki's Demi 2 attacks. Cast Big Guard immediately, and then get to attacking. With the Demi 2 attacks coming quick, Yuffie should have no problem getting her Limit Breaks. Even her Level 1 Greased Lightning will do well in the fight. Just keep Yuffie's health up, and this fight will be over soon. For beating Gorki, you will get an X-Potion.

Boss Fight: Shake

Make sure to set up Big Guard right off the bat. Shake has a Rage Bomber attack that can doo up to 600 HP damage. Big Guard will help cut that to around 300. You can use Choco-Mog to paralyze Shake, then let loose on him. He is actually a fairly simple fight. For defeating Shake, you will get a Turbo Ether

Boss Fight: Chekhov

For this fight, you want to equip either the Ribbon or the Jem Ring on Yuffie. This will prevent Chekhov from paralyzing her with his Stare Down attack. Start off with your trusty Big Guard, and go after him. Spells in this fight do work, but not as effectively as pounding him physically. Just keep the health and Big Guard up, and you will come out a winnder. For beating the third God, you will get an Ice Ring

Boss Fight: Staniv

This basically is who is the strongest fighter fight. Staniv does have a War Cry attack, but all ti does is cause Sadness. Set up your Big Guard, and let loose on Staniv. This might get a bit drawn out, since Staniv is a strong character defensively, but just keep at him. Cast Big Guard as it wears off, and keep Yuffie healthy. For beating Staniv, you will get an Elixir.

Boss Fight: Godo

Well, no one would have guessd that Yuffie would have to fight her father. This is not something she was overly thrilled with, and it showed in her not wanting to fight him. But Godo was not about to let his daughter slide. Before she could argue more, he set in with his Omni-Change, and the fight between father and daughter is off! You can see why this guy sits on the top floor...he is brutal! Start off the fight with Big Guard as soon as you can. If you have Regen in your magical stock, USE IT! With your Added Effect + Poison on your weapon, you should be able to Poison Godo. This will help speed the batle along a bit. Try casting Slow on him as well, if you have the materia. Anything that will give you more hits in than him. Godo has three faces, and each face has its own attack. The red face will hit Yuffie with Beast Sword. This is a pretty good attack for damage, and will do between 250 and 300 HP damage. It also has the ability to cast Trine. This spell will do close to 1000 HP damage. The golden face will cast Sleepel, and Mini on Yuffie. When Godo's HP gets too low it will also cast Cure 2 on itself. The white face will hit Yuffie with Drain, Bio 2, and Demi 3. Demi 3 is more lethal than that of Gorki, but it will not be so bad with the Elemental+Gravity on Yuffie's armor. Focus on keeping yourself healed above anything else. when your Limit Break becomes available, hit him with it. If you have any strong spells such as Comet (Forgotten City), or any level 3 of Fire, Ice, or Lightning, use them. Do not hold back on anything, because he will not hold back on you. If you find you are not getting on top of the fight, your levels might be too low. Head to the surrounding area of Wutai and do some leveling. Then you can try again to get the better of him. For defeating Godo, you will get Yuffie's All Creation Limit Break.

After the grueling fight, Godo and Yuffie seem to make up a bit. He then hands over the Leviathan Materia. Yuffie and him tell each other what they feel, and they seem to come to an understanding. Godo asks you to allow his daughter to continue journeying with you. Like you get an option here. As you all depart, Godo stops Yuffie one more time, and tells her to return to Wutai with all of the materia.
Like father, like daughter!

Da-Chao Cave

On Disk 2, durring your assault on the Underwater Reactor, you might have come across the Leviathan Sacles item. You might not know it, but there is a very good use for this strange item.
Take the item back to Wutai, and head for the Da-Chao Cave. Here when you approach the flames, the Dragon Gods scale will extinguish the flames revealing more of the cave. You can then go through the cave, and collect the Steal as Well Materia, and Yuffie's weapon, the Oritsuru.