Currently, there is one weekly flight from Cairo to Port Sudan on Saturdays. Almost every airline flies on a regular basis to Cairo. From Cairo, the connecting flight with Sudan Airways leaves at 7.00 pm and reaches Port Sudan in just under two hours. Otherwise you can take a flight from Cairo to Khartoum and then go by Sudan Airways to Port Sudan [ about an hour] , or by coach which will take much longer.
There are several flights a day from Khartoum to Port Sudan, costing about 400SDG
Every two weeks, a big event happens in Port Sudan...a train leaves! The station, which is normally deathly quiet and deserted, suddenly comes alive with passengers struggling with enormous suitcases, screaming children, and entire extended families waving relatives off. If you want to travel by train and would like to have a seat for the 18 hour journey, then get there early...three days before the train, all seats had been sold. if you can't get a seat, you can still board the train, and sit in the corridors or on the roof, but don't expect to get much legroom or sleep. It is an experience though, probably not one I'm rushing to repeat, but it did have its moments...like climbing out of windows to buy food on station platforms, watching the sun set over the Red Sea Hills and seeing it rise again in the desert, waiting an hour in the middle of nowhere while a search party went off to locate an unlucky snorer who rolled off the roof, making jam sandwiches with no spoon, etc....Tickets cost 2400 for 3rd class or floor space, 2900 for 2nd and 3300 for 1st class, or you could just buy a ticket to Jebeit in the mountains halfway.
Buses arive in Port Sudan from Kassala, Gedarif, Medani and Khartoum. The road may be good, but distances are long. On an expensive air-con bus like Pan Express or Afras, Port Sudan is 8 hours from Kassala, 16 from Khartoum. Cheaper buses are less comfortable, and of course take much longer. For that trip, I'd definitely recommend an air-con bus, as the weather is extremely humid once you pass through the Red Sea Hills and into the coastal plains. All buses usually leave their starting points before midday, often at 8am, although you can be lucky and find a bus later on...just you might not have much choice what sort of bus.
The Khartoum-Port Sudan buses tend to stop overnight just outside Kassala, where there is a restaurant and a few wooden beds to park your bum for a few hours. The security police won't allow you to enter the city itself...you'll have to make do with the views from afar...but they don't have any objections to you travelling through Kassala.
There might also be services to Atbara, but I have no idea how often they leave. Local buses run to the mountain resorts of Arkawit and Gebeit fairly frequently, and down the coast to Suakin...see my Suakin page for details of how to get there.
Most Europeans arrive by plane on Sudan Airways from Khartoum...they are not the most punctual in terms of being on time due to the restrictions the US has placed on selling Sudan aircraft parts. I took the bus from Khartoum which is roughly a 12 hour ride that departs around 06:00 from either Khartoum or Port Sudan....you will stop in Suakin going both ways to drop off or pick people up. The buses are modern with a/c and toilets (did not use one as I prefered the ones at the stops along the way)..lunch/breakfast is also served along with sodas and juice. My ticket cost me 65 SDG each way on Afras bus lines. The buses make numerous pit stops as the Gov't requires the drivers to log the stops as an effort to stop them from speeding thru the desert. If you are a tourist ie: non- local you will also need to get signed off with the local security where they will review your travel permits prior to letting you on the bus. Try and do this when you buy your ticket and get your seat a day prior to your trip. These buses fill up so don't expect to get a bus ticket day of.
We went to Port Sudan by road.The road was fine, but the journey was slow due to camels who shared the road as well. There is an airport just outside the town and Sudan Airways has regular flights, but it is expensive.