You need the heat gun. A soldering gun is used for soldering large individual solder joints, and it's completely unsuitable for reflowing BGAs like the PS3 CPU and GPU.
A Ball Grid Array (BGA) is a package type where tiny balls of solder (hundreds in the case of a CPU or GPU) cover the bottom of the chip and connect it to the circuit board. Unlike most packages which have leads protruding out the side, the BGA can use the entire bottom surface of the package to make connections. Because the connections are very short, the inductance can be kept minimal and thus higher speed signals are possible. BGAs are great from a purely electrical point of view. The downsides are mostly manufacturing and mechanical issues.
BGAs are a challenging sort of package to reliably solder in the first place. Because the solder joints are under the chip, it's also difficult to inspect them. It's easy to create a latent defect which doesn't initially affect electrical continuity, such as a dry joint, pass continuity and functional testing, work normally for a while, and then suddenly crack and fail. Allegedly this is what is happening with the YLOD.
The idea behind the YLOD fix is to simultaneously remelt all of the solder joints, and in the process restore the cracked joint to working order. It may work, it may not, and it may just totally ruin the board. The key to having a chance at success is that all the joints have to melt at about the same time, so that surface tension can pull the cracked joint back together.
The heat gun produces a stream of hot air, which you can use to evenly heat the chip and melt all the solder joints at once. The soldering gun delivers its heat by conduction from a relatively small hot tip. This works fine when soldering a single wire, but on a BGA it just creates a single hot spot, cooking that part of the chip and melting the closest joints, while the rest of the joints remain solid.