Appearances do not deceive in this case; Gyarados is definitely something to watch out for. It can come in very easily and set up with Dragon Dance, and unlike Salamence and Tyranitar, it has no trouble with Water-types at all. It has good tools in Taunt and Thunder Wave, and can even use gimmicks such as special attacking or a Choice Band to surprise and shut down common counters. A potential sweep is waiting for everyone who uses Gyarados; however, its biggest disadvantage is the popularity of its best counter, Zapdos.
Send this out against any Fighting or Water Pokemon, Dragon Dance up, then sweep. Taunt blocks Toxic and Thunder Wave; use it accordingly. Hidden Power Flying is generally superior to Hidden Power Rock, both for STAB and for the good type coverage it provides. However, Hidden Power Rock hurts Zapdos, who is one of Gyarados' main counters, and deals acceptable damage to Skarmory; Aerodactyl doesn't enjoy it either. The Speed investment guarantees +1 Gyarados outspeeds Raikou, who is the fastest OU threat it can beat without a Jolly nature—with the exception of Jolly Dugtrio, which isn't much of a threat.
12 EVs let Gyarados outspeed neutral base 100 Pokemon after one Dragon Dance. 100 EVs beats Adamant Tyranitar before a Dragon Dance, as well as Modest Raikou and all base 100s after a Dragon Dance. With 188 EVs, unboosted Gyarados beats Jolly Tyranitar, and +1 Gyarados outpaces Timid Raikou. 212 EVs let +1 Gyarados outrun positive-natured Alakazam, Dugtrio, and Sceptile, and 196 EVs along with a Speed-boosting nature beats out Adamant Heracross before a Dragon Dance, and all common OU Pokemon bar Ninjask after a Dragon Dance.
This set has significant surprise factor, and beats up several of the usual Gyarados counters. Use Thunder for Skarmory, Hydro Pump for Donphan and Solrock, and Blizzard for Zapdos. Ice Beam is an option if you are not feeling particularly lucky, but the difference is significant: Blizzard will do about 57%, and Ice Beam about 45% max. This set needs some luck to pull off successfully; try not to spoil the surprise too early. Hidden Power Flying does some damage to special sponges, and still makes Heracross cry.
This can hurt a decent variety of Pokemon, but prediction is obviously needed. Double-Edge wreaks havoc on Zapdos switch-ins and Hydro Pump takes care of Ground-types such as Donphan and Claydol, but note that Fire Blast only 3HKOes Skarmory. Run more Special Attack EVs to do more damage to these physical sponges.
Surf and Hydro Pump take down Donphan and Skarmory, and are viable options on the Dragon Dance set. Double-Edge is an alternative to Hidden Power Flying as it deals comparable damage to Flygon and Claydol, and can handle Zapdos as well. Paralysis is always a plus, so Thunder Wave is cool. Substitute can help Gyarados set up, but Taunt is arguably better as it prevents phazing as well. Gyarados can use the RestTalk combination to tank or set up Dragon Dance, but will have limited offense. Flail can be used alongside Substitute or Endure; if using the former, make sure Gyarados's HP is not divisible by 4. It works nicely with Gyarados's great Attack stat and Dragon Dance, and a +2 Earthquake can KO Metagross. Such a set would have a hard time with Tyranitar, though.
Checks and Counters
As previously mentioned, Zapdos is the best counter in the game to Gyarados. It resists Hidden Power Flying, is immune to Earthquake, and OHKOes Gyarados with Thunderbolt. Aerodactyl can do the same with its STAB Rock Slide, but it is weak to Water moves and doesn't have very good defenses. Jolteon is faster than Adamant Gyarados even after a Dragon Dance boost, and can OHKO it with Thunderbolt. However, it can't switch in easily as Gyarados might predict it and hit it with Earthquake.
Skarmory doesn't commonly carry any attack that hits Gyarados hard—the exception being the rare Rock Slide—but despite Taunt, it can beat Gyarados one on one with Drill Peck or Hidden Power Flying. However, it should beware of the occasional mixed or special Gyarados. If Gyarados lacks special attacks or Taunt, Toxic, Thunder Wave, and phazing moves will prevent it from sweeping. Weezing can be a prick to Gyarados in a similar vein to Skarmory. It can Will-O-Wisp Gyarados and Haze away its Dragon Dance boosts; if Gyarados has Taunt, Weezing can always Sludge Bomb, as repeated Sludge Bombs will eventually bring Gyarados down. If needed, it can even pack Thunderbolt to defeat Gyarados. Once again, as with Skarmory, Weezing does not like special attacks. Donphan can comfortably take several physical assaults, then Roar away Gyarados or hurt it with Hidden Power Rock or Rock Slide. It is easily dispatched by Surf or Hydro Pump, though. Although it is UU, Solrock is another decent counter to Gyarados thanks to STAB Rock Slide, along with a resistance to Hidden Power Flying and an immunity to Earthquake. Don't have it try to take a Surf or Hydro Pump though. Porygon2, Starmie, and Regice also survive Gyarados's attacks easily to counter with decently powerful Thunderbolts.
Choice Band Gyarados is best handled by prediction and capitalizing on the resistances of Pokemon such as Metagross, Zapdos, and Skarmory. Flail variants can get shut down by Tyranitar's Sand Stream, as well as priority. The special attacker is completely shut down by Lanturn, who not only packs STAB Thunderbolt, but is itself immune to Electric thanks to Volt Absorb, and further resists Water, Ice, and Flying attacks. Most other Electric-types, such as Raikou, Jolteon, and even Ampharos, can switch in and take out Gyarados with Thunderbolt. Zapdos must watch out for Blizzard or Ice Beam, though.
Gyarados can also fall easily to a surprise Electric-type move, such as Forretress's Zap Cannon. Claydol and Vaporeon are good users of Hidden Power Electric as they aren't hit hard by Gyarados's other moves, and accomplish something aside from hitting Gyarados. It lets Claydol hurt Skarmory, and enables Vaporeon to counter other bulky Waters more effectively.