NOT ALL IN ONE BASKET...
Assuming that the duration of their stay underground hasn't caused any mutations or lost of eye sight and whatnot. I would start by addressing the current status quo. Why has it shifted into a need to reach out from the safe zone, or more solidly, why is the safe zone no longer safe. This would most likely come about during a town meeting or similar.
Plan, vote, execute.
In a modern society to get anything done there is a committee who delegates and ultimately decides on the course of action, thusly creating the Plan. A vote on which of the committees ideas holds the best weight in the eyes of the people. They would focus on these 3 topics:
Method - most logically by foot, protected by clothes, carrying maybe a bedroll or tent. This is because the people have forgotten to pass down rounded education to their children and thusly now only have limited intellect.
Explore - teams of explorers, if possible multiple teams are best. Send one up, send one through. Have an "air team" and a "cave team" Where they each struggle differently in their own hostile environments. But when out in the real world explorers should be building waypoints or emergency bases. Places to run to in extreme situations when you can't get back to base. These waypoints could also eventually create a grid of safe spots used to travel and trade, possibly, as well as map markers. Because knowledge is power especially when passed down.
Educate - at this point education needs to be emphasized as lost intelligence is the worse thing any society can deal with. Schooling should be continued or emphasized as extremely valuable for survival. Especially by the experienced to the young.
The most logical path is explore ALL avenues and expect NONE to flourish. Do not put all eggs in one basket. I would hope the committee would agree that sending 2 or 3 or more search parties would be best. One via external extreme hostile environment, one via caves and tunneling, and more in other directions if possible. Small teams of 5 to 10.
That said, the cave exploration would stop quickly once they reach a material harder than handtools will allow them to cut through. It would take decades to tunnel with handtools any real or usable distances. Explosives would speed things up but could cause more damage than help.
Luck would have 1 team find an underground river complex, a reason to send multiple exploration parties. Rivers are like roads and can be utilized for travel and trade. Obviously they would need to be able to build boats.
Luck would also have a 2nd team find old not yet collapsed abandoned subways, or sewers if near a major city. Using the rails or water to carry trade goods.
Luck would also have a 3rd team find pre-existing tunnels within the natural gas mines. Maybe stumbled upon once depleted.
Logically though no one would return without a plan.
All of that said is why I, as a member of that important committee, wouldn't put all my eggs into one basket. Think of it like this, its easier to hit an unknown target in pitch darkness with a shotgun rather than with a handgun.