I'm too lazy to write out a plot explanation so I'll give you the Wikipedia Plot Explanation:
The plot of Gyo centers around the "death stench", a revolting smell first encountered in connection with creatures appearing to be bizarre fishes with scuttling, sharp metal legs. At first they appear merely as smaller fishes, but later also as larger sea creatures such as sharks and even a whale.
The creatures are eventually revealed to consist of a small metallic, legged structure with the carcass of a dead animal (and later, human) strapped on top. Germs infecting the rotting body produce a gas - responsible for the terrible smell that surrounds the creatures - that makes the metal construct move.
Later, it is found that the Japanese Army was researching germs that produce the death stench during World War II in a desperate effort to turn the tide of the war. Infection by the germ produced large amounts of foul-smelling gas from body tissue, and since infection quickly killed the test animals, walking machines were built to carry them further, allowing them to reach and sicken enemy troops. Enemy planes sunk the ship carrying the prototypes for the walking machines, which ran entirely on the gas.
Underwater the machines have attached themselves to the fish and moved from the island to the mainland, attacking the humans. Later it is found that the death stench gas might have a will of its own, and that the machines are not man-made: the disease has apparently mutated to be able to construct the walkers from the metal hulls of sunken battleships.