When you get the Tiny Bronco, there are many places that you can now explore. In fact, before going off to Wutai, you should find your way north to the Icicle Area and the Bone Village. They sell Rune Armlets there, and if you're interested in growing lots of materia, it's always nice to have four double-AP slots around. They also provide decent armor, compared to the Platinum Bangles you've probably been using up till now. If you're planning to get any Master Materia later, you shoul come here and stock up on Rune Armlets now, instead of later.
When you've gotten everything you want from here, go back down to the ocean to the west of Rocket Town with the Tiny Bronco. You should be within sight of a beach to the west. Go ahead and park it there. Although you should note that this next section is totally optional, I really think that it's worth the extra hassle. You will need to have Yuffie around to do it, though, so if she's not with you now, you can always get her later and come back. Just remember that this scenario does hold several valuable treasures, and you cannot do it in Disc 3, only 1 or 2.
After you land on the beach, head north. You won't get far before Yuffie starts telling you about what lies ahead. Right about now, some Shinra soldiers will attack you. During the fight, Yuffie steals all of your materia (well, not all--if you have huge amounts of them, she'll leave you with a couple of magic materias). In order to get it back, you're going to have to make the dangerous trek all the way north to Wutai Village. On the way there, though, you'll have to fight some pretty nasty enemies. However, some of these enemies give you some invaluable items that will help you on your quest. In particular, watch for the Bizzare Bugs, which, when killed, give you an X-Potion for each one you killed. If you want to survive the trip to Wutai, use characters with relatively high vitalities, use Hypers, have everyone equip thir most powerful weapon (Cloud should definitly use the Yoshiyuki now), and fight conservatively. If you are ever horribly out matched, don't hesitate to run. Eventually, you should make it to Wutai.
Now, your task is to find Yuffie when she hides. She'll hide in several different places aroud the town before you can finally corner her. Also, the weapon shop won't sell anything to you until she rejoins you. You can go visit the famed Turtle's Paradise, where you'll meet your old pals, the Turks. Fortunatly for you, they're on vacation, so they won't give you any trouble. Talk to them for a while, then leave and head for the building just northwest of the bar. Before you enter, talk to the little girl wandering around outside by the save point. She'll give you a clue to where Yuffie is hiding. Now go in. The Materia Shop is notably absent of Materia, but you can buy some spell-casting items here, and opening the chest will bring out Yuffie, who'll run for a new hiding spot, taking with here the MP Absorb materia that was in the chest. Head west to the other half of the city, and enter the set of apartments on the right. Search around here good, as there's a secret passage (look closely, you'll see it), which contains a Hairpin, a weapon for Red. There's also a guy name Godo who says some cryptic things. Keep hassling him until the secret comes out. The next place you'll find Yuffie is in the very first house on the right, by the entrance to the town. She's crouching behind the little screen. Finally, when you walk by the Turtle's Paradise, you'll notice a pot outside shaking around. Go up to hit and inspect it. Your team will automatically move into position to cut off Yuffie's retreat, and she'll take you back to her house. When she tells you to pull the right lever, do it. You'll be trapped, and she'll flee again. (It doesn't matter if you pull the left lever or right, as both will spring the trap.)
Don't worry, just hit either of the 2 levers again and chase after her. Btw, downstairs in Yuffie's house is the last Turtle's Paradise poster, so if you've seen the others (The first in Midgar sector 6, the second in Shinra HQ, the third in the Gold Saucer Ghost Hotel, and the fourth and fifth in Cosmo Canyon) you will able to collect your reward. (In case you're wondering, the reward is a Magic, Speed, Power, etc. source, and a Megalixer.) If you missed any of them, though, don't worry. You can always go see them and come back later. Note that you have to have read the flyer about the prize outside of the Turtle's Paradise before you can collect it.
To find Yuffie again, go to the little gazebo with the big gong across from Godo's house on the west side of town. Climb up the stairs and look at the little gong and lever. Cloud will bang the gong, and a secret passage will open up for you. Go in and watch how the events play out. Anyway, follow Corneo, then negotiate with the Turks. Go up to the moutains (the path going northwest from the save point) and do a little exploring. You should discover a little cave with some fire and a Dragoon Lance for Cid here--remember this place, because you just might find a way to make the fire subside later in the game. You'll also eventually discover Yuffie, Elena, and Corneo. He'll sick a boss on you, who shouldn't be too hard to take out if you're in good shape. Rapus is immune to Fire, so don't bother with that. Just use limit breaks and regular attacks. Once you've defeated him, the Turks will aid you be taking out Corneo. Yuffie and Elena will be saved.
Well, you've got your materia back, plus a couple new ones, so take the time to rearrange it all again. The weapon shop is open to you now, and so is the little shed with the cats in it. If you go up to the top floor here, you'll find an HP Absorb materia. Also open now is the big pagoda at the end of the street on the west side of town. You'll need to take Yuffie with you, though. You can do this part later when you're stronger, but why not take the challenge and do it now? Suit Yuffie up with all the good materia, like an Enemy Skills (for Big Guard, White Wind, etc.), Poison, Restore, HP Plus, and some powerful attack spells like Odin. Giving her a Hyper might be a good idea, especially if you have the Limit Break Bloodfest (lv. 2) or, even better, Doom of the Living (Lv. 3). Now you're ready to attack the pagoda. The first four enemies are not hard at all. Just use Big Guard on yourself, then unleash your most powerful attacks on them. After each fight, I'd recommend healing Yuffie up. Godo, though, is a whole other ball of wax. Big Guard yourself, then cast Bio2 or 3 on him right away, until he's poisoned. The problem with Godo is that eventually he will heal himself. You're going to have to find a way to stop him from doing that. One way is to let the poison do its work, but that takes a while. A better way is to either use a mirror (gotten from the Mirage enemy in Nibelheim's Shinra Mansion) or cast Reflect on HIM to keep him from curing himself. When he's beaten, you'll get Yuffie's level 4 limit break manual and the Leviathan materia. (If you want to know the secret to winning this whole thing in about 2 minutes, wait until you get the sub. Go down to the Downed Shinra Plane, get the Conformer, then return to Wutai. Yuffi will kill almost everyone with one stroke, except for Godo. He takes two, I think.)
When you're finished in Wutai, go back to your plane and head for the Gongaga Area. Remember that little house where no one was home? Well, the owner's there now, so talk to him. He'll tell you where you you can find that Keystone, which you'll now need to do.