I always have the generic HM slave (Zigzagoon, Bibarel, fuck you Patrat for not being a good slave and for gen V, PanWaterthing), then I have a water pokemon in my team for surf, and a flying pokemon for fly.
Replaying Emerald. I have a little 3-Zigzagoon army (in fact, 2 Zigzagoon and a Linoole) having distributed Cut, Strength, Secret Power, Surf and Rock Smash between them. Also, they work as a small Pickup squad providing me of Rare Candies relatively often. Really useful non-battling creatures. Why three, because (I think) that increase the odds of any of them picking up an item, and also they have different levels for different items). Already got 18 Rare Candies thanks to them.
In White, Volcarona is my "nurse" for hatching eggs (Flame Body) and Flying transport. For Surfing I have a Panpour, and Haxorus is my "hunter", using False Swipe to catch Pokémon easier.
On another game (for some reason I got both English and Spanish White) I had a Cubchoo to Surf because none of the Unova water Pokémon convinced me, except by Samurott and Panpour, but I started with Tepig on that game.