Originally they were part of a larger heart called the Purity Heart, which then was split into the eight smaller Pure Hearts.
Each time Mario gets a new one, he has to put one in a Heart Pillar when he finds them in order to unlock a new world.
Here are all eight locations of the Pure Hearts:
- Red: Merlon gives it to you when you start.
- Orange: Fracktail guards this Pure Heart's location. After you defeat him, you can go see Merlumina, who then gives it to you.
- Yellow: Merlee gives it to you when you defeat Mimi.
- Green: Tippi produces it when you get her back from Francis as a response to her newfound trust in Mario and Co.
- Blue: It was kept in outer space (in the Whoa Zone), and Squirps guides you to it.
- Indigo: It was kept by the Floro Sapiens before they gave it to Mario.
- Purple: King Sammer had it but when their world ended, it became stony and unresponsive. Mario went (or rather Dimentio sent him) to The Underwhere to revive it.
- White: Luvbi, a Nimbi, was actually the last one after all. After she has a fight with her parents (who aren't actually her real parents, since she is a Pure Heart), she resumes her Pure Heart form and Mario obtains it.