You can technically start this quest when you reach any of the locations where the UFO can be spotted (see below), which in two cases is after Balamb Garden becomes mobile. To complete the quest, however, you'll need to acquire the Ragnarok in disc 3.
Your first objective is to spot a UFO at four different locations across the globe:
Kashkabald Desert - the large desert at the far eastern end of the Centra continent, due south of Esthar city.
Mandy Beach - east of Timber. You're not looking for the long, slender island off the coast, but rather the actual beach nearby. Just run along the water's edge here until the UFO shows up.
Trabia Heath Peninsula - east of Trabia Garden, you'll find a sandy peninsula, northeast of which is a small, rather drab island. Land on this island and you should encounter the UFO again.
Winhill Bluffs - head to Winhill and run around the fields east of the town.
Note: Note that you don't have to unequip Enc-None for this - the UFO is one of the few encounters in the game that ignores it.
Encountering the UFO
After you've seen the UFO in those four locations, head over to the Grandidi Forest, which if you did the Chocobo Forest sidequest is the last forest you visited. It's at the northeastern end of the Esthar continent, at the end of a long peninsula - east of Trabia Garden, north of the Lunar Gate. You'll know you're in the right area when you find some highlands completely covered by forest. Find the actual Chocobo Forest - a small ball of forest rising about the rest of the foliage - and land on the mountain behind it (northeast of) it. You should encounter the UFO here, and this time, it's a fight!
Well... kind of. The UFO doesn't do much in the way of fighting back. Beat it up until it's dramatically destroyed and you'll score an Aegis Amulet for your troubles.
Make sure you have five Elixirs (you can buy them from the Esthar Shop!!! for 37,500G each, or if you used Card Mod on the Angelo Card, you should have more than enough) and the Item command equipped, then fly to Balamb Island and land near the crater where Balamb Garden once stood. Explore the edge of the crater and you should find... an alien? The alien - PuPu - will beg for Elixirs. If you toss five of them at the little alien it'll thank you, leave, and reward you with the PuPu Card. If you defeat PuPu in combat instead, you'll score an Accelerator while if you use Devour on it the devouring character will gain a permanent +1 bonus to Speed. Still, the PuPu Card is unique, and the other gains are not - if you ever want to complete your card collection, you'll need to get this card.
You can use Card Mod to refine the PuPu Card into a Hungry Cookpot, which you can use to teach a GF the Devour ability, should you desire.
Note: If you want to earn the "Collector" achievement for acquiring all the cards, do not lose or refine the PuPu Card. You can win back every other card in the game except for this one, and you must have one of each card in your possession at the same time.