Route 22. You will need Surf, Waterfall and Strength to get to it.
If you look around a while you will find a trainer who is standing in front of a river. Defeat them if you haven't already, go past the waterfall and continue south. Go past the island, Earthquake isn't there. You will come to an island with a Strength puzzle on it. If you complete it, you fill find the TM containing Earthquake.
