Cloud can obtain his ultimate weapon, the Ultima Weapon, by destoying Ultimate WEAPON. Confused? On Disc 3 you can find Ultimate WEAPON, hovering over a lake in the eastern continent.
Barret's ultimate weapon, the Missing Score, can be found on the steps that lead up to the Sister Ray just before he team encounters Hojo.
After getting the "Key to Sector 5," you can return to Wall Market and check the broken vending machine again. It's fixed, sort of. It dispenses Tifa's ultimate weapon, the Premium Heart, and then breaks down again.
While wandering around the Temple of the Ancients you'll find Aeris' ultimate weapon, the Princess Guard, just off the clock room. It's at the end of the IV hallway.
After taking Bugenhagen to the Ancient City, return to Cosmo Canyon with Red XIII in your party. He finds Bugenhagen in pretty bad shape, but Red XIII walks away with his ultimate weapon, the Limited Moon.
During the team's second raid on Shinra's Headquarters, you can pick up Cait Sith's ultimate weapon, the HP Shout, from a locker in the health spa located on the 64th floor. The locker is on the left side of the third row.
When you have the submarine, locate the crashed Gelnika just off the coast by the Gold Saucer. Inside the generator room is Yuffie's ultimate weapon, the Conformer.
After the rocket in Rocket Town has been launched, talk to the old man outside the Item Shop. He's th one who's been so obsessed with the rocket. If you speak with him several times, he'll eventually give you Cid's ultimate weapon, the Venus Gospel.
After acquiring the submarine or a Gold Chocobo, you can reach Lucrecia's Cave, located behind a waterfall in a lagoon in the Nibel area. Visit the cave with Vincent in your party during Disc 3, revisit the cave with Vincent in your party to get his ultimate weapon, Death Penalty.