Known facts
As of now, the origins of the Dragon eggs are up to speculation. First we have as Marcus Swope says:
"What are they?" she asked, her voice hushed and full of wonder.
"Dragon's eggs, from the Shadow Lands beyond Asshai," said Magister
Illyrio. "The eons have turned them to stone, yet still they burn
bright with beauty."
AGOT - Daenerys II
So Illyrio believes or was told by the vendor that those eggs are from the Shadowlands beyong Asshai.
It is quite possible that Illyrio might be right. Dragons after all existed all over Essos (And even Westeros) before the rise of Valyria and there are some theories that Shadowlands beyond Asshai may have been the place where Dragons' origins lie (Disputed by Valyrians and Qartheen).
In such fragments of Barth’s Unnatural History as remain, the septon
appears to have considered various legends examining the origins of
dragons and how they came to be controlled by the Valyrians.
The Valyrians themselves claimed that dragons sprang forth as the
children of the Fourteen Flames, while in Qarth the tales state that
there was once a second moon in the sky. One day this moon was scalded
by the sun and cracked like an egg, and a million dragons poured
forth.
In Asshai, the tales are many and confused, but certain texts—all impossibly ancient—claim that dragons first came from the Shadow, a
place where all of our learning fails us. These Asshai’i histories say
that a people so ancient they had no name first tamed dragons in the
Shadow and brought them to Valyria, teaching the Valyrians their arts
before departing from the annals.
Yet if men in the Shadow had tamed dragons first, why did they not
conquer as the Valyrians did? It seems likelier that the Valyrian tale
is the truest.
But there were dragons in Westeros, once, long before the Targaryens came, as our own legends and histories tell us. If dragons did first
spring from the Fourteen Flames, they must have been spread across
much of the known world before they were tamed. And, in fact, there is
evidence for this, as dragon bones have been found as far north as Ib,
and even in the jungles of Sothoryos. But the Valyrians harnessed
and subjugated them as no one else could.
TWOIAF - Ancient History: Rise of Valyria
Speculation
With the recent release of Fire & Blood, I believe we have found the answer to this question even though it is not explicitly mentioned.
King Jaehaerys I had granted Dragonstone to his sister Queen-Dowager Rhaena Targaryen where she took up residence with her daughter Aerea, her sister in law (Actually her secret lover) Elissa Farman and other courtiers. Elissa wanted to sail the sunset sea but lacked the coin to buy the ship that she had in mind. She asked Rhaena Targaryen to foot the bill but Rhaena refused to do it. Elissa found another way. There were Dragon eggs in the Targaryen Stronghold and each was priceless. Elissa stole three eggs and made her way to Braavos because the city was famed for ship-wrighting.
After failing to track down Elissa, Rhaena took wing to inform her brother the King about the theft. Jaehaerys was alarmed and ordered agents to be sent all over Essos and offer rewards for any news of the Dragon eggs. Jaehaerys was seriously concerned about what would happen if the Eggs found their way to Volantis and the Old blood of the city managed to hatch them. Not too long ago it had taken an Alliance of Essos and Westeros to defeat Volantis who wanted to revive Valyrian Empire, even Aegon the Conqueror participated on his dragon. He decided that at any news of Dragons hatching in the East, he'd demand their return. If that country did not return them, Jaehaerys would declare war.
Elissa Farman departed for Driftmark the next morning. From there she took ship across the narrow sea to Pentos. Thereafter she made her
way overland to Braavos, whose shipwrights were far famed, but
Rhaena Targaryen and Princess Aerea had no notion of her final
destination. The queen believed she had gone no farther than
Driftmark. Lady Elissa had good reason for wanting more distance
between her and the queen, however. A fortnight after her departure,
Ser Merrell Bullock, still commander of the castle garrison, brought
three terrified grooms and the keeper of the dragon yard into Rhaena’s
presence. Three dragon eggs were missing, and days of searching had
not turned them up. After questioning every man who had access to
the dragons closely, Ser Merrell was convinced that Lady Elissa had
made off with them.
[...]
She sent men to Driftmark, only to learn that Lady Elissa had sailed
to Pentos. She sent men to Pentos, but there the trail went cold.
Only then did Rhaena Targaryen mount Dreamfyre to fly to the Red Keep
and inform her brother of what had transpired. “Elissa had no love for
dragons,” she told the king. “It was gold she wanted, gold to build a
ship. She will sell the eggs. They are worth—”
“—a fleet of ships.” Jaehaerys had received his sister in his solar,
with only Grand Maester Benifer present to bear witness to what was
said. “If those eggs should hatch, there will be another dragonlord
in the world, one not of our own house.”
“They may not hatch,” Benifer said. “Not away from Dragonstone. The
heat…it is known, some dragon eggs simply turn to stone.”
“Then some spicemonger in Pentos will find himself possessed of
three very costly stones,” Jaehaerys said. “Elsewise…the birth of
three young dragons is not a thing that can easily be kept secret.
Whoever has them will want to crow. We must have eyes and ears in
Pentos, Tyrosh, Myr, all the Free Cities. Offer rewards for any word
of dragons.”
“What do you mean to do?” his sister Rhaena asked him.
“What I must. What you must. Do not think to wash your hands of this,
sweet sister. You wanted Dragonstone and I gave it to you, and you
brought this woman there. This thief."
[...]
“Should the dragons turn up, anywhere from here to Yi Ti, we will
demand their return. They were stolen from us, they are ours by right.
If that demand should be denied, then we must needs go and get them.
Take them back if we can, kill them if not. No hatchlings can hope to
stand against Vermithor and Dreamfyre.”
[...]
Grand Maester Benifer said, “You are speaking of waging war across
thenarrow sea, Your Grace. The costs—”
“—must needs be borne. I will not allow Valyria to rise again. Imagine
what the triarchs of Volantis would do with dragons. Let us pray it
never comes to that.” With that His Grace ended the audience,
cautioning the others not to speak of the missing eggs. “No one must
know of this but we three.”
Fire and Blood: Birth, Death and Betrayal Under King Jaehaerys I
Elissa sold the Eggs to the Sealord of Braavos and got her ship.
She took on a bastard name of her own devising, calling herself Alys
Westhill. Under that name, she secured an audience with the Sealord of
Braavos. The Sealord’s menagerie was far famed, and he was glad to buy
the dragon eggs. The gold she received in return she entrusted to the
Iron Bank, and used it to finance the building of the Sun Chaser, the
ship she had dreamed of for many a year.
Fire and Blood:
Birth, Death and Betrayal Under King Jaehaerys I
Meanwhile in Westeros, due to another emergency, the search for the dragons was called off and agents were given new tasks. But Eventually, the word reached the Red Keep due to Elissa Farman's own mistake of calling port at Old Town. Given the ship's unique design, Jaehaerys was certain that Braavos had bought the eggs and built the ship.
Jaehaerys sent his Hand Septon Barth to Braavos to negotiate the return and threaten Braavos with utter destruction if they refused. The Sealord countered with his own threat (That even though Braavos cannot fight the Iron Throne, he would send the Facelessmen after the Targaryens to avenge his city) and managed to cut a deal that as long as Dragons did not hatch, Jaehaerys would let him keep the Eggs. If Dragons did hatch, the Sealord would return them. In return for the understanding of the King, Braavos would have the Iron bank waive off all the loans of the Iron Throne. Since the throne was drowning in debt from the reigns and wars of Kings Aenys and Maegor, Barth agreed. The issue never came up again given that no dragons hatched and presumably they just assumed that the eggs must have turned to stone.
Two centuries later three stone eggs happen to find their way to a "Pentoshi Spicemonger" Illyrio Mopatis just as Jaehaerys had said. Those are probably the three eggs that were stolen from the Dragonstone and unbeknown to Daenerys, they were her connection to the legacy of her ancestors and her roots all along.