Unfortunately the border between Eritrea and Sudan is firmly closed at the moment. In October 2002, there were attacks on the Kassala area (including the Sawagi) by Sudanese rebels based in Eritrea's mountains, and since then there have been periodic skirmishes along the border. To add to that, the closest town in Eritrea, a place called Tessenei, has had bombings recently, three in the last month (November 2003). The border was rumoured to be reopening, but don't hold your breath! When it is open, buses run from Kassala as far as the border post, where apparently you can walk across to Tessenei. When it does open, I will definitely be one of the first to cross...tales of espresso, spaghetti bolognaise and Melotti beer in Asmara have whetted the appetite!
The only way to get around Kassala, if you don't want to walk, is by a motley assortment of local buses, collectively known as muwaasilaat (transport). The important bus routes to know are Khatmiya (to get to old Khatmiya and the mountains), Banat (for the Gash River, University HQ, Sikka Hadeed and Souq Gharb el-Gash) and the special buses for Sawagis Janubiyya and Shamaliyya. Buses to Souq ash-Sha'abi, the long-distance bus station, start running about 6am. All buses run from the central bus station, an unmissable jumble of traders, juice stall and makeshift buses. Buses can be flagged down anywhere on their route, and cost 30 dinars.
From Khartoum, head to Souk ash-Sha'abi where you'll find all the buses and ticket offices waiting for a silly khawaja like you to come along so they can try to rip you off. Buses to Kassala generally run in the mornings...the last bus leaves around midday because it is illegal to enter Kassala under darkness (after 7 or 8pm). The journey takes 8-9 hours and goes via Wad Medani and Al-Gedarrif. Take my advice and take a comfortable bus...they are really not that comfortable, but I bet the basic buses are much worse and much much slower. The air-con buses cost around 30,000 pounds (3000 dinars or US$15)...and you get a TV, radio, drinks and food. Make sure your travel permits are in order, and try to make local friends if they are not!