The young ninja Yuffie can be found in any forest on the World Map. She is encountered like a random monster and must be defeated like one too. The battle is not too hard, but if you do have problems, try an Elemental-Fire materia combination on your armor. The first forest you come across is after passing through the marsh, past the Midgar Zolom, and through the materia cave you reach the world map again. Here there is a forest close by. However, I have often found that you cannot encounter Yuffie here. The forest South of the Gold Saucer is a better place to try.

After the battle, you will find yourself on a plain with Yuffie and a save point. DO NOT use the save point, or even open the menu as you'll be taking your eyes off Yuffie and she'll be gone with a lot of your gil. Speak to Yuffie and you will be given a number of options during the conversation. In order to get Yuffie to join your party, chose the following options during the conversation:

Yuffie: "You Spikey Headed Jerk! One more time, let's go one more time!"
Cloud: Not interested.
Yuffie: "You're pretty scared of me huh!?"
Cloud: Petrified.
Yuffie: "I'm really gonna leave! REALLY!"
Cloud: Wait a Second!
Yuffie: "You want me to go with you?"
Cloud: ...That's right.
Yuffie: "All Right! I'll go with you!"
Cloud: ...Let's hurry on.