My version is Omega Ruby. I tried the water west of Mossdeep in v1.0, both via leveling up and by Rare Candying, and it didn't work. I also tried Route 134 via leveling up and Rare Candying and it still didn't work.
So I tried a few different things; I encountered a Trainer near Shoal Cave and evolved Wailmer during the battle, and that didn't work, but maybe that route doesn't work anyway. I also made Wailmer learn a move by level up (Bounce at level 45) before the evolution west of Mossdeep. Sadly that didn't work either.
Someone said this works with Carvanha. I know an NPC implied surfing with it is different, I've yet to Surf with Carvanha though.