The bus station is a little off the town. Also busses passing through may drop you off at a smaller bus stop at a rail crossing. From here you can get a service taxi to the town center for 50pt. A taxi from either of the bus stops to the town center will cost you 5–10 LE. To Port Tawfiq will set you back 10–15 LE.
The Arafat in Port Tawfiq has single rooms starting from 35 LE and is conveniently located in the Port area if you're planning to take the ferry to Saudi Arabia.
Some other budget hotels are in the area of Sharia Nimsa (take a service taxi on sharia al-geish and ask to be dropped off there). Heading northeast for some blocks you'll get to Hotel Medina with single rooms starting at 90–100 LE. Right next to it is Hotel Shahin with rooms starting at 35 LE. However, the owner speaks only very few words English.
Find out the bus schedule at the main bus station. A daily bus to Dahab (40 LE, 7–8 hours) via Al-Tor and Sharm-Al-Sheikh leaves at 11am.