I did some research and collected various answers:
From about.com there are two possibilities:
Air: As stated, access to Canaima National Park is by air to the
village of Canaima, about 50 km away from the falls. From there, you
take either a smaller plane and fly to an airstrip at Canaima Lagoon,
or travel by river to the lagoon. From the lagoon, you hike to a view
point of the falls.
There are also daily flights via Puerto Ordaz connecting Canaima
airstrip with the major cities of Venezuela. The airstrip is a short
jeep-train ride from nearby Lodges. Check flights from your area to
Caracas or other Venezuelan cities with connections to Ciudad Bolicar
and Canaima. From this page, you can also browse hotels, rental cars,
and special deals.
Water: From Canaima, when the water is neither too high or too low,
you can travel by motorized canoe, called curiara up the Carrao River,
then the Churun river to an point where you can then hike through the
jungle to the falls. The river portion takes about four hours, and you
should allow an hour or more for the hike. Canoe access to Angel Falls
is restricted to the rainy season, June to November.
Angel Falls is one of Venezuela's top tourist attractions, though a
trip to the falls is a complicated affair. The falls are located in an
isolated jungle, and a flight from Puerto Ordaz or Ciudad Bolívar is
required to reach Canaima camp, the starting point for river trips to
the base of the falls. River trips generally take place from June to
December, when the rivers are deep enough for the wooden curiaras used
by the Pemon guides. During the dry season (December to March) there
is less water seen than in the other months.
Very interesting information can be found on Backpacker-Tours. They do not only explain how to get there but also mention a price and duration. Similar information can be found on World of Waterfalls. They also explain in very detail how to get there.