Things You'll Need
Instructions
Wild Capture
Surf on Route 129, and, rarely, Wailord will appear.
Battle Wailord to lower its HP. Use status-effecting moves that cause Sleep or Paralysis, as these increase the chance of capture.
Throw a high-quality Pokeball, such as an Ultra Ball, when Wailord is weakened and either asleep or paralyzed. You can try catching it without the status effects but may need to use more Pokeballs.
Evolution
Go to Mosdeep City and talk to the man in the northernmost house to get the Super Rod.
Go fishing with the Super Rod. Wailmer appears in a number of fishing spots, including the water near Mosdeep City, and just east of Lilycove City. You can also fish in Dewford Town, Slateport City, Pacifidlog Town and EverGrande City, as well as the Seafloor Cavern and Shoal Cave. Wailmer also appears along a number of routs, including Routes 105, 109, 110, 121 through 134, and several others.
Catch Wailmer. Battle until Wailmer's HP is low, then either paralyze it or put it to sleep. Use an Ultra Ball or other good-quality Pokeball for the actual capture.
Put Wailmer in your party and raise it to level 40, at which point it will evolve. If you would rather not use Wailmer on your team, you can take it to the Pokemon Day Care center outside of Mauville City on Route 117. Each step you take translates into one experience point for Pokemon in the day care, so it may talk a lot of walking to get Wailmer to level 40 this way.