They're pretty hard to come by. You can smash rocks in places like Tohjo Falls, which can also give you good things like Max Revives. There is one you can get on Route 32. They can be obtained through Pickup, but the earliest level is at 51. Luvdiscs have a 50% chance of holding one, but they only appear on Route 27 during a swarm. Getting 1000 points at the Pokeathlon on Sunday or Wednesday will also net you a Heart Scale, but this only works a few days of the week (obviously), making it unreliable the rest of the week.
Rock Smash is your best bet, followed by Pokeathlon, but it'll take a long time.
Source
Hope I helped!