After you regain Cloud, you'll notice a large creature floating above a crater near Junon. This creature is the Ultimate Weapon (the same one who attacked you in Mideel), and to get Cloud's most powerful weapon, you're going to have to take him out. He looks very imposing, but actually, Ultimate isn't very hard, especially compared to Desert and Underwater Weapons. To destroy him, you need only make a few preparations, and he will be gone in no time.
I equipped my people like this. You don't need to use the exact same characters, because the only really important thing is arranging your materia.
Cloud: I gave Cloud the Heaven's Cloud, Imperial Band, and Ribbon. For Materia, I gave him 2 mastered HP pluses, a Long Range, W-Summon with Zero Bahamut, and a mastered MP Plus.
Cid: I gave Cid the Scimitar, Imperial Band, and a Ribbon. For Materia, I gave him 2 mastered HP Pluses, a Long Range, Lvl.2 Comet w/Quadra Magic, an Enemy Skills, and a mastered MP Plus.
Yuffie: I gave Yuffie the Conformer, Minerva Band, and a Ribbon. For Materia, I gave her 2 mastered HP pluses, 4x Cut, and Steal.
To begin the battle, just fly the Highwind into Ultimate when he's sitting still.If he's in the air, you'll fight on the deck of the Highwind. (Just for laughs, try casting Alexander during this battle. It'll tear up the ship.) Just hammer him with your most powerful attacks, and eventually he should fly away. Now your task is to find him again.when you do, just fly into him until he begins to fly in a straight lie towards a place. (Where he goes is random.) When he settles over a given location, just fly into him to start the battle again. Eventually, he will settle over the desert by Cosmo Canyon. This is the final battle, and you can now kill him.Fight him as normal, but try your hardest to get the person equiped with the Enemy Skills strike the killing blow. Ultimate will cast a spell called Shadow Flare on this person. You can learn this skill later from the Dragon Zombies in the Northern Crater, but why not get it now?
After you've killed Ultimate, you'll receive Cloud's most powerful sword, plus a whole slew of Exp. and Gil. After the battle, there was supposed to be a short FMV showing Ultimate's explosive death, but all we get to see is a giant crater in the ground. This crater is important, however, because it gives you access to the Ancient Forest, a little bonus town with some great prizes.
With this information at your disposal, you should be able to polish off Ultimate Weapon with no trouble at all. If you have any questions, however, just post them on the message board.