Airplane: Currently, the closest service is via Vietnam Airlines to Dong Hoi, check their website for latest fares and flight times.
Train: Several arrivals and departures at Dong Hoi daily from as far away as Hanoi and Ho Chi Minh City, only a few hours from Hue.
Bus: A local bus goes from Dong Hoi to Phong Nha for 40,000 VND. It departs at 14:00 from Nam Ly bus station. The bus back to Dong Hoi leaves Phong Nha at 8:00, so you have to either stay overnight or try to go back with one of the tour buses (they may even take you to Dong Hoi for free).
Motorbikes: Motorbikes can be rented for 150,000 VND from hotels in Dong Hoi. It takes about 1 hour via a highway that has little traffic: the Phong Nha cave is about 45 km from Dong Hoi and the Thien Duong (Paradise) Cave is about 70 km from Don Hoi.
Taxis: can be hired from hotels/resorts, airport or train station in Dong Hoi. About 1 hour on a highway with cars, oxcarts, motorbikes, buses, trucks.
Hotels in Dong Hoi can arrange day trips to the park.
Phong Nha and Tien Son Caves: It costs 80,000 VND for the entrance fee to see each cave (160,000 VND for both) and 350,000 VND to rent a boat for up to 14 people to visit both caves (or 320,000 VND for the boat to only one of the two caves). (prices as of October 2012) You can share a boat with other tourists that show up. Renting a boat is a requirement as there is no other way to get to the caves. Caves are exquisite and very large. It is about 45 km by road from Dong Hoi and takes about an hour by motorbike. More information on Wikipedia: Phong Nha Cave and Tien Son Cave.
Nuoc Mooc Spring Eco Trail: 50,000 VND for ticket. Transportation can be negotiated to take you there from Phong Nha village. Buy ticket at the hut under the sign off the road, then wander the bamboo bridges and paths along both sides of the river/rapids. Go back to see where the river springs up out of the ground. This is also on the road to the Thien Duong (Paradise) Cave.
Thien Duong (Paradise) Cave: Newly paved road off the main HCM Highway provides car/motorbike/bus access. Buy 120,000 VND ticket to enter; the fee includes an English speaking guide. Just after that, separate >>optional<< ticket for non-polluting electric golf cart to the base of the stairs (if nice weather, walk along the new path of about 1.6 km instead). Approx. 500 stairs up to entrance of cave, another 100-200 stairs down inside. Stunning, tastefully lit cave features along 1.1 km of new (spring 2011) wooden pathways. It is about 70 km by road from Dong Hoi and takes about an hour and a half by motorbike. Some claim that this is among the most beautiful caves in the world. More information here on Wikipedia.
Bicycling and kayaking, swimming at allowed points along the rivers.
Thien Duong Cave: Along with the new road, several restaurants -- at the site entrance, as well as at the top of the 500 stairs! -- were being built for visitors in Spring 2011.
In Dong Hoi, there is a range of hotels/guesthouses, as well as at least one beach resort. About 1 hour travel time from Dong Hoi to the park.
At least two idyllic options very close to the park:
Chay Lap - clean, quiet, no frills homestay, excellent Vietnamese home cooking, outdoor showers, will set up trekking bicycles and kayaks for you. Website has a great map of activities in and near the park.
Phong Nha Farmstay, Cu Nam Village in Bo Trach, ☎ 0944759864, . Comfort out in the rice paddys. Run by English speakers. Laidback, backpacker idyll. Experience local life or chill out.8-35USD.
In Phong Nha Town near the cave boat dock there are several budget level guesthouses along the road TL20 (intersection with the giant sign that says Phong Nha Ka Be National Park) for around 150,000 dong or more.
Trang An Hotel Two star hotel found right before the entrance into the national park area with a bright neon light visible from the HCM Trail at night. Wifi is free. Doubles with private bathroom, air conditioning and fridge for 350,000 dong.
Check park regulations first, or go with an organized tour. Park rangers are very suspicious of undocumented visitors overnighting in the park.
Be cautious driving on the road to/from Dong Hoi; avoid night driving.