The events of the episode The Lich would imply that they came from wherever the Enchiridion came from. Since the gems combine with the Enchiridion, it's logical to assume they were created together. This would indicate they are all incredibly old, as Simon had the Enchiridion pre-Mushroom War. However, given the cosmic magic that was unleashed when they were combined, it's entirely possible that they don't originate on Earth or even Earth's universe.
The sequence of events in The Lich also provide a hint for why the princesses each have a gem. By keeping the gems separate, it provides a measure of security that helps prevent anyone from bringing the gems and the Enchiridion together. Given that Princess Bubblegum's tiara protected her mind from the Lich, and the Lich was the one who stole all the gems and Enchiridion, it's likely the Lich is the reason the princesses all have the gems.
Given their likely ancient and possibly extra-universe origin, it seems likely the gems don't just protect the princess' minds. However we haven't seen the gems' powers revealed except for their mind protection ability and interaction with the Enchiridion.