You need to collect 5 badges before you get HM03
When you first arrive in Petalburg City, you're not able to challenge the gym leader there, who tells you to come back once you have 4 other badges. Only once you have done that and returned to beat the Petalburg Gym, getting the Balance Badge, will you be given HM03. You'll know you've reached this point when your trainer card shows the appropriate badges and the doors at the back of the first room of the Gym are unlocked.
If this is your first time in Petalburg, having just defeated Wally for the first time, you should continue to the northwest towards Rustboro, then eventually to the southwest to speak to Mr. Briney to reach Dewford.