Very few locals know street names and addresses, and you are likely to have to get directions in terms of landmarks. Botswana doesn't have a postal delivery system to addresses just to centralised mail collection points, so even when streets are well-marked, the names may be unfamiliar to residents.
Through a combination of coaches and combies, you can get anywhere in Botswana without any trouble, though public transport is spotty away from big cities and major axes but hitchhiking is popular and very easy. However, hitchhiking should only be done in desperate circumstances, as Botswana driving is often very erratic and it can be a harrowing experience to have a stranger drive you somewhere. It is advisable to arrive at the bus station quite early, as the busses do fill up quickly, and it is not uncommon to spend several hours standing in the aisle waiting for a seat to free up remember to bring water, as the buses are often not air conditioned.
The roads are paved and well maintained, so travel by car is also not a problem, provided that one keeps a close eye out for the cows, donkeys and goats that spend much time in the middle of the road.
The Trans-Kalahari Highway is an old cattle route, now newly paved and easiy drivable with a 2-wheel drive. It runs from Lobatse to Ghanzi in Botswana, making the connection from Windhoek, Namibia to Gaborone, Botswana. It is a long and uneventful drive, but you get a good feel for the Kalahari Desert. Fuel is available in Kang at the Kang Ultra Shop, which also offers a respectable selection of food, overnight chalets, and inexpensive camping.
Be aware that the road from Maun to Kasane through Chobe national park is an unpaved sandy track, even though some maps show it as a proper road. You need a 4x4 for this route. Going via Nata to / from Kasane/ Maun is much quicker and easier.
Buying a car. Botswana isn't a bad place to buy a vehicle for a multi-month long trip around southern Africa, which you can then sell at the end. Botswana is considerably cheaper than South Africa and Gaborone is swamped with second-hand Japanese and UK imports. The paperwork is not too daunting and the dealer can do most of it for you. Websites like Want a Car can give you a good idea of prices.
Beware of the many corrupt police officers which are posted at check points, as they often try and claim fines of up to Pula 1000,00 for allegedly ignoring a stop sign or other offenses. Be polite, stay calm and respect their assumed authority when being pulled over.
Also, the country is divided by many veterinarian fences, which are set up to break the spread of cattle diseases foot and mouth and so on. There, you are required to surrender all fresh meat products, drive through a disinfectant pit to cleans your tyres and rub your shoes on a disinfectant solution too. Depending on the month and situation, sometimes these posts are not manned, but at times the checks here can be thorough.
There are many bus companies in Botswana. One of the biggest is Seabalo (http://www.seabelo.bw). From Gaborone you can travel by bus to any bigger city in Botswana.