This gym uses Fighting Pokémon so either use Flying or Psychic Pokémon. When you win, talk to Ckuck's wife, the lady outside, and she will give you Fly. Now fly to Goldenrod City, you might want to go to Bill's house for an Eevee, if you haven't colleced it as yet.
When you get here, there will be a puzzle with the boulders, here is how to solve it, just move the two at the sides in and push the middle one left or right.