Internal travel permits are a thing of the past, so once you've gotten into Saudi, the country is your oyster. There are, however, three exceptions:
Many archaeological sites around the country, eg. Madain Saleh, require permits. The National Museum in Riyadh issues these free of charge, but you should apply at least a week in advance.
The area around Makkah and Madinah is off-limits to non-Muslims; conversely, those on Hajj visas are prohibited from leaving the area and transit points like Jeddah. The exclusion zone is well signposted.
Some remote areas, notably around the Iraqi and Yemeni borders, are restricted military zones. You're exceedingly unlikely to stumble into them by accident.
Within cities, taxis are the only practical means of transportation. Standardized throughout the country, metered fares start at SR 5 and tick up at SR 1.60/km, but outside Riyadh you'll often have to haggle the price in advance. Solo passengers are expected to sit up front next to the driver: this has the advantages of being next to the full blast of the air-con and making it easier to wave your hands to show the way.
The railway network in Saudi Arabia is seriously underdeveloped, with only one line running between Riyadh, Al-Hofuf and Dammam, but it's still the only passenger train service in the entire Gulf. There are plans to extend the network to Jeddah and build a Makkah-Madinah link during the next few years.
The trains are operated by Saudi Railways Organization (http://www.saudirailways....) and have 3 classes: Second, First and the delightfully named Rehab. First and Second classes are very similar, with aircon and two-by-two seating, but First has a few inches of extra legroom. Rehab VIP class, on the other hand, has plush leather seats, roof-mounted flat-panel TVs showing Arabic entertainment, and slick waiting lounges at stations. There are no reserved seats, so show up early to claim yours, and beware that most carriages reserve the forward-facing seats at the front of each carriage for families. Trains have a cafeteria car serving up drinks and snacks, as well as push-trolley service.
A ticket from Riyadh to Dammam costs SR60/75/120 in Second/First/Rehab. There are four trains each day in both directions, and the trip takes 4-5 hours. Note that, as of May 2008, the timetables on SRO website are outdated. It is advisable to buy tickets in advance as the trains are often sold out. You can reserve tickets by calling their service center in Dammam +966 3 827 4000 and then pick up the tickets from the nearest railway station 24 hours before departure.
Saudi Arabia is a large country, which makes flying the only comfortable means of long-distance travel. State carrier Saudia has the best schedules, with near-hourly flights on the busy Riyadh-Jeddah sector 90 min and walk-up one-way fares costing a reasonable SR280 ~US$80. Low-cost competitors Nas (http://www.flynas.com/) and Sama (http://flysama.com/) can be even cheaper if you book in advance, but their schedules are sparser, changes will cost you money and there's no meal on board.
Car rental is available and gasoline is some of the cheapest in the world. Highway quality is highly variable, except highways that connect major cities, which are generally excellent. However, there are important reasons to think twice about car rental. The country has some of the highest accident rates in the world. Accidents are common, and if a visitor is involved in one, they would be exposed to the extremely punitive Saudi legal system; see elsewhere on this page for the warnings about that.
If you are involved in a car accident all parties are required to stay where they are and wait for the Traffic Police call 993 to turn up, which can take up to four hours. English is unlikely to be spoken by the police, even in big cities, so try to use the waiting time to arrange a translator. The police will issue an accident report, which you have to take to the traffic police station and get it stamped a few times in different queues this takes most of a morning. Only then can any damage to the car be repaired, as insurance companies will not pay for any body work without this report.
It is not uncommon for the traffic police to resolve the incident there and then by determining the guilty party and deciding compensation. So, should it be your fault the Police will ask you to pay an amount to the other party - but you are not obligated to do so.
At the present time, access to car rentals is limited to males 21 and older. Women cannot drive on public roads or ride bicycles.
The Saudi Arabian Public Transport Company SAPTCO (http://www.saptco.com.sa/) operates long-distance buses linking together all corners of the country. Buses are modern, air-conditioned and comfortable, but often slow, and the bus stations are more often than not located several kilometers away from the city center. The Riyadh-Dammam service, for example, costs SR60 and takes around 6 hours.
Special "VIP" services operate on the Riyadh-Dammam and Riyadh-Bahrain sectors. For a surcharge of about 50%, you get a direct, non-stop city center-to-city center services, plush seating and a meal on-board -- all in all, quite good value, if the sparse schedules match your plans.