The firestone was first discovered by Ayla. It's name as we know it is Iron Pyrite.
While living alone in her valley Ayla's fire went out. As she was making herself some tools she was distracted and by mistake picked up a piece of iron pyrite instead of her hammer stone. When she hit the flint she was working on she was surprised to find that a spark appeared. this gave her the idea to restart her fire that way.
These stones are given as valuable gifts during their journey. Most of the Zelandoni, if not all, use firestones by the end of "The Shelters of Stone" though it may not be as common with Zelandonii who live further away from the Ninth Cave.