Hacer un equipo en torno a un pokémon no es algo tan sencillo como "Un equipo con Mega-Gyarados lleva A, B y C". Para empezar, ¿para qué formato quieres el equipo? ¿Combates simples? ¿Combates dobles? ¿6 vs 6? ¿3 vs 3? ¿4 vs 4?
Al jugar con Mega-Gyarados supongo que Gyarados tendrá la habilidad Intimidación. Básicamente porque la primera vez que Gyarados entre en combate podrá hacer uso de ella y bajar el combate. En combates dobles puedes usar una combinación de dos pokémon que tengan Intimidación (como Salamence, Landorus tótem, Arcanine o Mawile) y bajar el Ataque a la mitad a ambos oponentes.
También debes plantearte cobertura de tipos. Dado que Mega-Gyarados es Agua Siniestro, te vendrán bien pokémon que cubran tus debilidades (Eléctrico, Planta, Bicho, Hada y Lucha). El equipo necesitará un tipo Fuego (cubrirás las debilidades Planta y Bicho) así que Arcanine si es para formato de dobles estará bien. Acero también te vendrá bien porque aunque no es efectivo, es resistente a Planta y Hada (aunque débil también contra lucha).
También debes plantearte roles en el equipo. La mejor forma de hacerlo es viendo que objetos utilizar en combate. Yo siempre me planteo al menos utilizar cuatro objetos: Una megapiedra (en tu caso para gyarados), un movimiento Z, unos restos/lodo negro (para un pokémon tanque) y una vidaesfera (para un atacante principal).
Y con la información que has dado, es a lo máximo que yo puedo ayudarte. Espero que te haya servido

.
¡Un saludo!