Each character has an Ultimate weapon here is were you find them all

Cloud- Cloud will receive his Ultimate weapon once you defeat the monster Ultimate WEAPON. This monster is found hovering over the lake on the eastern continent

Barret- Barret will get his ultimate weapon on the steps leading to Hojo in Midgar. Keep in mind that you need him in your party in order to see the box containing the weapon in the first place.

Tifa- After getting the "Key to Sector 5", you can return to Wall Market and check the broken vending machine again. It's fixed and gives you Tifa's final weapon.

Aeris- You can get this in the temple of ancients. Just off the clock room at the end of hallway IV.

Red XIII- After taking Bugenhagen to the Ancient city, return to Cosmo Canyon with RedXIII in your party. Bugenhagen gives Red XIII his ultimate weapon.

Cait Sith- During the team's second raid on Shinra HQ you can find Cait Sith's ultimate weapon from a lock on the 64th floor. The locker is on the left side 3rd row down.

Yuffie- Once you get the sub, locate the crashed shinra plane off the coast of gold saucer. Yuffie's weapon is inside the generator room.

Cid- At rocket town there is an old man staring at the rocket. Talk to him and keep talking until he gives you Cid's ultimate weapon.

Vincent- Go to lucrecia's cave during disk 3 to get Vincent's last weapon.