Gyarados learns attacks in multiples of every 5 levels, just for future reference. (so level 20, 25, 30, 35, etc.) however, his movepool through leveling was quite bland in Pokemon Crystal. (judging by the tags on the question, I assume you're playing Pokemon Crystal.) It has a wide movepool in TMs, so teach him a TM or two, because it really does help pump up your aquatic beast.
I hope I helped you out! :)