Their origins certainly are mysterious, not much is really revealed. The most I can really say is that the credits of Cave Story refer to them at the "Mysterious native inhabitants of the island." As for how old they are and what magic they might posses, that is unknown as well. I guess it's one of those things Pixel left for the player to decide.