Go up north after she stole your orbs until you reach a town. After you enter you'll see her and she'll take off. go into the northeast into the next screen and enter the building on the right. Find the sleeping guy and talk to him a few times. yuffie will take off a couple of times. Go to the bar and talk to the turks. I'm not sure if this is posible after you return to midgar. then go to what they call a materia shop, check the chest and yuffie will steal again. Go to the first house you see when you first enter Wutai. Talk to the man and check the curtain like thing and you'll spot her. Go towards the pub and youll spot a shacking pot.
You still don't have her. after your out of the cage, go to the large bell in the northeast part of town and ring it. go into the door. After all is said here go to the shop and buy as many of those bolt 2 fire 2 spells as you, atleast 5 each. Go to the statures north of the save point and search around til you find the boss fight. Use those items I told you to buy or if you didn't all you can really do is attack.