Heartstone is found around the Bedokaan Village. Wander around their swamps (not on World Map) for a while and look for silvery stones. Get at least three of them while you're there.
Sometimes General Store clerks have them, including Black Diamonds and Geodes, ive seen Kathoryan Crystals (Sp)