Steps
- Get the Red Scale first. It comes from the Red Gyarados at Lake of Rage.
- Travel to Route 30.
- Talk to Mr. Pokémon and he will hand over the Exp. Share.
The Exp. Share lets a held Pokémon earn experience without battling, which helps a slow Pokémon like Pineco catch up.
One answer also said it can be won as a lottery prize, but the Mr. Pokémon route is the reliable way.