The quest took about 300 years and started in Nar-Voth (Dwarves of Golarion, p. 17).
When the dwarves of Nar-Voth began their Quest for Sky,
not all of their people were convinced of the wisdom of
tunneling upward, and some steadfastly refused. As
time went on and the questing dwarves moved farther
toward the promised surface lands, they and the holdouts
who remained behind grew further and further apart
culturally, and, eventually, physically.
Surprising, I know. But we have only the faintest idea of how vast the Darklands are. Digging through the safest and closest area of the darklands took 300 years, and dwarves are skilled miners. Imagine how long it would take to dig from the deepest reaches of Orv.
According to Into the Darklands (which also describes that orcs and dwarves had kingdoms in Nar-Voth), Nar-Voth extends down to about 2,000 feet. Which means that the dwarves took their sweet time to get out of there. Of course, there weren't any natural tunnels until then, I believe, and they were the first to dig through all that.
The fall of the Starstone at the advent of the Age of
Darkness changed the world of Golarion forever, and these
changes were not limited to the surface world. The impact
of the Starstone was felt throughout the Darklands—and the
upper reaches of Nar-Voth in particular. Many caverns and
passageways under what is now the Inner Sea were destroyed,
along with a large portion of the underground orc empire.
For unknown eons before this event, the orcs and the
dwarves, two races that had vied for control of these caverns
for as long as either could remember, ruled the caverns of
Nar-Voth. Where the dwarves were masters of tactics and
defense, the orcs were fecund and warlike. No matter how
many orcs the dwarves slew, more grew up to replace those
lost. And no matter how often the orcs assaulted the great
dwarven city-fortresses, the dwarves always rebuilt.
According to Into the Darklands as well, the Duergar also took several old dwarven fortresses back, and the book shows us three of them:
Fellstrok and Hagegraf are both connected by the Long Walk, which is a major tunnel that serves as a trade route for several races in Nar-Voth.