There was an early claim that there is some magic tree that grows a Devil Fruit every thousand years or so. Similarly, there are stories about the "Sea Devil" being the origin of the powers. There is no real justification for these and they can be taken as in-story myths. We essentially don't know if they are true or not.
What we do know is that when a Devil Fruit user dies, its ability is transferred to a regular fruit in close proximity. This is shown when the Salamander Fruit eaten by Smiley regenerated into an apple as it died. This regeneration cycle explains why all these fruits are scattered everywhere and how they continue to exist.
This does not explain where the fruits came from however. It seems from out-of-universe statements by Oda that Vegapunk will soon (if not already I'm not up to date on the manga) explain the origins of the fruit. This and the existence of artificial Devil Fruits indicate that more in depth knowledge about their origin and nature is known among the scientific elite of the New World. This information has not, however, been revealed to the reader.
For the specific case of the Fire-Fire Devil Fruit: when Ace died, another piece of fruit of the same kind somewhere near Marine HQ became a Fire-Fire Devil Fruit. This was eventually obtained by Doflamingo and brought to Dressrosa as a means to flush out Luffy. As the military was in control of the battleground, I would expect they had fruit available to absorb the powers and gave this one to Doflamingo as part of the plan. Alternatively Doflamingo or someone else could have carried fruit with them during the battle to collect the powers themselves.