Originally posted by Black Mage 121
Keep getting in to random battles around Winhill until PuPu appears. Then, do the same on Mandy Beach (South East of Timber), then again in the Kashkabald Desert (North of the Cactuar Island). Then you go to Grandidi Forest and find him again.
You can actually encounter the UFO battles with Enc-None equipped. Sometimes you get them as soon as you enter the area with that.