You should get Yuffie just after you've visited Fort Condor for the first time, and before you go to Junon Harbour for the first time. The forests in which you have to roam around in to find her are in between those 2 villages. There's a small one and a big one.