The first encounter can't be tracked and must happen by chance.
When you've encountered it once, you can track him by viewing the location on it's pokédex page, figure out a pattern, and try to get on the same route he is.
You'll need to encounter him 12 times before he dissapears from the map. After that, he'll be at the Sea Spirit's Den where you can catch him.