This one will be one of the more annoying ones. I suggest having a lot of Hi-Potions and Phoenix Downs, as well as having at least Celes and Terra know Holy and/or Firaga. Also, anyone in your fighting party should NOT have a level divisible by five (that is, ends in "5" or "0"), for ease. Level them up otherwise. Okay, hunting it. You'll want to land the airship so that it is perpendicular with the northern border of the map. Restart flying and tap the D-Pad left so it turns a few degrees and speed ahead. Why? Well, there are 4,096 tiles on the world map; only two that are next to each other are occupied by the Deathgaze, who cannot be seen. Eventually, you will run into him and fight.
Deathgaze can use a basic attack, Venom Claw (which can cause Poisoning), Aero, Death, and Lv. 5 Death . Each battle begins with Lv. 5 Death.
Okay, for the majority of this battle, you'll just want to focus on having Terra, Celes, and other major spellcasters use Firaga and/or Holy. Your others have certain other ways to go if they aren't good with magic: Sabin can use his Phantom Rush (if you have it), Cyan can use his Tempest (if you have it), Edgar can use his Drill, and Gau can use his Io Rage.
There are very high odds of the Deathgaze Fleeing battle, so there is very little point in doing anything but attacking, unless you get very low on HP. With each second turn, there is a one in three chance that the enemy will stick around. Progressively, your chance to get an X-turn (where X is another even number) are: 100%, 33.3%, 11.1%, ~3.7%, ~1.2%, ~0.4%... So, no more Deathgaze? No; he'll just occupy another place on the overworld map. He'll remain with the same stuff as he did at the end of the previous fight.
Find him as before: you'll want to land the airship so that it is perpendicular with the northern border of the map. Restart flying and tap the D-Pad left so it turns a few degrees and speed ahead. Eventually, you'll find him and battle him. Keep on battling him until he is defeated; shouldn't take but about three battles.
After the battle, you'll receive the Bahamut Magicite. SWEET!