This article is from the Final-Fantasy and other Square Soft Games FAQ, by firstname.lastname@example.org (Nick Zitzmann) with numerous contributions by others.
First, get in the Highwind and look for the newly-created lake near
Junon. The Ultima Weapon will be there. Crash the Highwind into it and
attack it. When it escapes, follow it as it swerves around in the air.
What you need to do is ram it 4 or 5 times, at which point it will stop
flying back and forth and fly straight to a certain, random location.
Fight it again, and keep repeating this until the Weapon makes it's
final stop at Cosmo Canyon (the number of fights you have to go through
depends on the amount of damage you inflict on it before it escapes).
After the battle at Cosmo Canyon, it will be dead for good.