There isn't really an "easy" way to get Heart Scales.
Here are a couple of ways to find them though:
- Dig Underground
- Use the Dowsing Machine Poketch App (usually near beaches, shallow water, and shoals)*
- Show the man at the Solaceon Newspaper the Pokemon he wants for the article, and he'll give you one along with some random types of pokeballs (Timer, Dusk, etc.) If you do it this way, you can get one Heart Scale a day!
So, my advice is to first get all the Heart Scales you can find by using the Dowsing Machine, and also do the Solaceon Newspaper thing every single day (until you don't need anymore Heart Scales). And once on a while go digging underground.
*Using the Dowsing Machine, here's a list of locations Heart Scales can be found at.
Route 213, Route 222, Route 223, Route 224, Route 226, Oreburgh City, Victory Road
Serebii has the locations