Getting Around Eritrea

As is well documented, the visa you obtain to visit Eritrea only lets you travel to Asmara. You need to visit the Tourist Office on Harnet Avenue and apply for a tourist travel permit for the other places you'd like to visit. This costs 20 Nakfa and we obtained it the same day we applied (go early in the morning). When writing where you'd like to visit, be as extensive as possible (make a list before going in). They scored a few places off our list (Lake Badda and surrounds) due to security issues, but happily approved the others. To get a permit you need a photocopy of your passport and Eritrean visa (ideally bring with you, but there are stationary shops in Asmara where you can get copies). Once you have your travel permit, photocopy it a few times - you are asked to show it at large numbers of checkpoints throughout the country and some, eg. Filfil, demand a copy or they won't let you through (though don't have photocopy facilities themselves). The checkpoints otherwise seem to be just a formality, but make sure you do always have your travel permit to show, as they are diligent at checking.

It seems to be easy to travel around the country by pubblic transportation. Small buses run almost everywhere, from early morning to late afternoon. Probably it takes time to visit the country just by pubblic buses. If you need a car with driver I recommend Gebrehiwet Waldemariam. He is a nice man, good driver, always ready to help, and can provide minibus, 4X4 WD, cars. More over, despite what you can think about African people, he is always on time, even a bit earlier. Unfortunately, travel by car could be expensive for fuel is very expensive in the country.

As of 2004, the only land border of Eritrea open for travellers was the one with Djibouti.
There are shared taxis between Assab in Eritrea and Moulhoule in Djibouti, with connections to Obbock.

The Sudanese border was only crossed by locals illegally during my visit, but reopened in late 2006. It remains to be seen how long it will stay open, and you need travel permits to reach the border towns (Kassala in Sudan and Tesseney in Eritrea) from either side.

The heavily militarized Ethiopian border is as tightly sealed as they get.

The Italians built a good railway network in Eritrea under their rule, but it has fallen into disuse later on.
However, since independence the Eritrean givernment has restored the extremely scenic line between Asmara and Massawa. Unfortunately there are no scheduled services anyway (probably because the buses are faster). Your only hope is tagging along for a ride on services chartered by tour-groups.

There is an extensive and cheap bus service around much of Eritrea. Fares are incredibly low: around 1 USD for a 3-4 hour long journey! Of course, at these prices you can't expect much in the way of comforts.

Should you need those comforts (or flexiblity), you can either hire a car to drive yourself, or hire a taxi with a driver to take you around.

Many travellers are hoping to catch a boat between Massawa & Sudan/Egypt, and Assab & Yemen.
However there are no passenger boats on either of these routes, and even if you found a cargo ship going your way, burocracy might stop you from taking it!

Eritrea is only served by a few airlines.
Of the neighbouring countries it is connected to Sudan, Djibouti and Yemen (but not Ethiopia!), while in Europe Rome, Milan, Amsterdam, and Frankfurt (and by now perhaps London) have direct flights.
Some of the cheapest flights to Eritrea tend to be on Egypt Air via Cairo.

I have been to the Dahlak islands for snorkelling and general sightseeing. Even if this was close to 4 years ago, I assume the situation is much the same as Eritrea has gone from one economic-political crisis to the other and not much has happened in tourism development and investment. I guess that my description may still hold water...
It is straight-forward to go Dahlak. You have to obtain/pay a national park fee, not so much. They know all the logistical stuff and routines and contacts at Dahlak Hotel in Massawa.
You need to rent a boat (ensure it has a canopy, otherwise you'll get fried) with a captain/guide. Bring a packaged lunch or make a booking for lunch/overnight at the Luul Hotel at Dahlak Kabir island.Bring water, lots and lots of water to drink. Ensure you have good snorkelling equipment - what we saw in terms of fins, snorkels and masks were quite rudimentary. Better bring your own. Ensure that the captain steers the boat really where you want to go. They prefer to do a very short trip, quick stop and return. Get a map, a plan and make sure that the plan is paid for and understood by the boat owner and would-be-captain. Cost was 250 USD pp for a whole day when I went there - 4 personsand one of us was a local. Should come down when there are more people.
Typically, the boats for hire are roomy, maybe space for 10-12 and diving equipment (or TVs and DVD players from Yemen), twin outboards and with 230 hp they'll hurtle you to the main Dahlak archipelago in about 1 1/2 hrs. You will see leaping dolphins on your way.
Some islands are closed for visitors for military and environment protection reasons. Your permit obtained in Massawa will licence you to land only on some of the islands.