Each character in the game has an Ultimate Weapon. They are typically the most powerful attacking weapon for each character and they all have 8 paired Materia slots with no Materia Growth. Having no growth makes them useless if you are looking to level up your Materia with AP so you should avoid them other than for fights where AP is immaterial.
They are perfect for late game fights including the final battle against Sephiroth, battles in the Battle Square Arena at Gold Saucer or against either of the Weapons (Emerald Weapon or Ruby Weapon), the two most difficult fights in the game.
So where can you find them?
Cloud’s Ultimate Weapon is called 
Ultima Weapon and you can obtain it by defeating Ultimate Weapon (more than a little bit confusing). Ultimate Weapon (the boss) is first fought in Mideel when you go to find and rescue Cloud after the battle at the Northern Crater / Whirlwind Maze.
It reappears again after you have defeated Diamond Weapon just before parachuting into Midgar, though it is much easier to defeat Ultimate Weapon after you reach the end of the game on Disc 3. Click on the link below for more information about this side quest:
The attack power for this weapon is based on Cloud’s current HP and his maximum HP. For example, the most damage is achieved when Cloud is at 9999/9999 and would be significantly less damage if Cloud were at 6702/9999. As a side note, the weapon actually changes color depending on how much HP Cloud has and how much damage it’s doing. The exact formula for calculating the damage is:
[ ( 3 * Power * Current HP ) / Max HP ] +1
Barret’s Ultimate Weapon is called 
Missing Score and it can be found when the team returns to Midgar to fight Dr. Hojo. The chest containing Missing Score can only be seen and obtained if Barret is in your party. Unfortunately, there is no way to return to this area of Midgar if you missed picking it up on your way through which means that there is no means to obtain Missing Score if you are already past this point in the game.
The attack power for Missing Score is based on the amount of AP the Materia equipped on it has. For example, if you equip level 1 
Lightning Materia with 526 AP on it Missing Score will do significantly less damage than if you had attached a MASTERED Lightning Materia. The formula for the weapon’s damage is:
[ Power * ( Total AP attached to Weapon / 10000 ) / 16 ] + 1
Tifa’s Ultimate Weapon is called 
Premium Heart. Premium Heart can be found by revisiting Midgar using the Key to Sector 5. Use the link below for more information on the side quest to return to Midgar. It is located in Wall Market in the little hut labeled “Item” that previously had the malfunctioning security gun when you first visited the area on Disc 1.
The attack power of Premium Heart is based on how full Tifa’s Limit Break gauge is. The fuller the gauge the more damage she will do. It is also multiplied by whichever Limit Break Level Tifa is on so make sure to get Tifa’s Limit Breaks leveled up. For more information on how to get to Limit Level 2, 3 and 4 check out the Learning Limit Breaks section in the Tips and Tricks area. The formula for calculating damage is:
[ Power * ( Tifa’s Limit Level * Limit Break Bar Level / 16 ) / 16 ] + 1
Princess Guard, which is Aeris’ Ultimate Weapon, can be found in the clock room of the Temple of the Ancients. You do not get much of an opportunity to use it with her though so don’t worry about it if you missed this item.
The attack power of this weapon is increased if other characters are KO’d, which makes it useless, but considering you never get to equip it, it’s already a useless item. The formula for calculating damage is:
(x2 for every character that’s KO’d)
All you have to do to obtain Red XIII’s Ultimate Weapon is revisit Cosmo Canyon on Disc 3. The weapon itself is called 
Limited Moon. There are also a few other items available when you return to Cosmo Canyon - check out the “returning to Cosmo Canyon” page for more information.
The attack power of Limited Moon is based on Red XIII’s MP. The closer his MP is to his maximum MP (full) the more attack power he will have. For example, if Red had 635/635 MP Limited Moon would do more damage than if he had 723/999 MP. The formula for calculating the weapon’s damage is as follows:
[ ( 3 * Power * Current MP ) / Max MP ] + 1
You can obtain Yuffie’s Ultimate Weapon, 
Conformer, by making a visit to the Sunken Gelnika which can be accessed after you have completed the Underwater Reactor section of the game and obtained the Shinra Sub as an accessible vehicle. Check out the Sunken Gelnika side quest section below for more information:
Conformer’s weapon damage is based on what level of the enemy that you are attacking. If you are fighting a high level enemy the weapon will do more damage. This makes Yuffie’s regular attacks extremely powerful against late-game bosses (including Sephiroth, Emerald Weapon and Ruby Weapon). The formula for calculating weapon damage is as follows:
( Power * Enemy Level ) / 16
Cid’s ultimate weapon is called the 
Venus Gospel and it is one of the easiest Ultimate Weapons to obtain. All you have to do is talk to the old man found in Rocket Town when you return to Rocket Town later on in the game. This can be done anytime after you have gone up into space and returned with (or without) the Huge Materia.
The attack power of the weapon is determined in the same fashion as Red XIII’s - it is based off Cid’s MP bar. The closer Cid’s actual MP is to his maximum MP the more damage it will do. For example, if Cid has 597/597 the weapon will do more damage than if Cid had 701/999 MP. The formula for determining the damage is:
[ ( 3* Power * Current MP ) / Max MP ] + 1
Death Penalty, Vincent’s Ultimate Weapon and Vincent’s Level 4 Limit Break, 
Chaos, are obtained at the same time. They are obtained in Lucrecia’s Crystal Cave which can be reached anytime after you have obtained the Shinra Sub as a mobile vehicle (after the Underwater Reactor portion of the game). Click on the link below for more information on how to complete the side quest:
The damage this weapon inflicts is based on the number of enemies Vincent has killed throughout the game. It doesn’t matter which weapon he kills them with, the game is keeping track of them all. The more enemies Vincent has killed the more damage that will be inflicted. The formula for calculating the weapon’s damage is:
[ Power * ( Kills / 128) / 16 ] +10
Cait Sith’s Ultimate Weapon is called 
HP Shout. It can be retrieved during the second visit to Midgar in the Shinra Building towards the end of Disc 2. HP Shout, just like Missing Score, cannot be obtained if you miss them during your second visit to this area. There is no way to obtain them without restarting the game.
The attack power of HP Shout is based on the difference between Cait Sith’s current HP and his maximum HP. Therefore, when fully healed up, HP Shout will do the most damage.
[ ( 3 * Power * Current HP ) / Max HP ] + 1
