Khubu Island, Makgadikgadi salt pan Inset: Basarwa lighting a fire, Rock art at Tsodilo Hills. © Jacob Knight
It is likely that people have been living in the Shoshong hills for over a million years, long before other continents were inhabited. Modern humans (homo sapiens) are thought to have originated in East Africa about 200,000 years ago. 
Around 40,000 years ago, as the first modern humans began to reach Europe, groups of San people (sometimes called Basarwa in Botswana) were living in small scattered groups, collecting wild fruits and insects and hunting animals with spears. At some point they were joined by the Khoe (sometimes called Bakgothu by Batswana) who herded sheep and cattle. Rock paintings and other traces of these early people can be found at Tsodilo Hills, and their modern descendants are thought to be genetically the oldest population of humans in the world.
A large lake called the Makgadikgadi Superlake occupied an area to the north of Shoshong until geological changes diverted the rivers which fed it, and it eventually dried out in stages about 10,000 years ago, leaving the smaller salt pans which we see today. 
Bantu people arrived from the North in around 500 AD bringing knowledge of metal working and probably crop agriculture. They traded and intermarried with the Late Stone Age people they found in Botswana.  Iron was mined in many areas including the Tswapong Hills, specularite at Pilikwe (near Palapye) and gold and copper further afield, and traded for ivory and other goods. Traces of iron working can be found in the Shoshong hills. 
ToutsweAround 800 – 1250 AD a rich chieftainship developed occupying large villages set on hilltops. The ruling families lived in three main villages; Toutswemogala, Bosutswe and Sung, which was just north west of Shoshong near what is now Sung ward. The residents on the hills owned many cattle, wore dyed cotton robes and may have had servants. Some Batswana customs such as paying bogadi (bride price) in cows are thought to date from this time. 
Peasant farmers lived on the plains, but some probably also owned their own cattle.
There is also evidence of a prehistoric settlement on Pitsane Hill, around 15km north west of Shoshong.
To the east of Toutswe, another chieftainship known as the Mapungubwe developed. They established great trading networks through modern day Mozambique to the Indian Ocean. 
These people may have later moved further east to modern day Masvingo in Zimbabwe where in around 1200 AD the Zimbabwe state was established. Zimbabwe took control over the trade routes and become rich. The large town of Great Zimbabwe was built soon after 1250 and by 1350 had 11,000 inhabitants or more. At its peak, the state covered a huge area larger than modern Botswana, probably extending as far as the Shoshong hills.
illustration by J. Theodore Bent who published a description of the Great Zimbabwe ruins in 1892 (passing through Shoshong en-route)..
The decline of Zimbabwe started around 1420, and Great Zimbabwe had been abandoned by 1500. Around this time, the State of Butua was established which lasted until 1840. The Butua are the ancestors of the Kalanga people in modern day Botswana. It is likely that Kalanga people occupied the Shoshong area. 
There are traces of stone walls and cairns on the hills above Shoshong. As John Mackenzie observed in 1864:
References[1,3,5,6] Tlou T & Campbell A (1997) “History of Botswana.” Macmillan
 McIntyre C (2003) “Botswana.” Bradt Travel Guides
[4,7] Parsons N (1973a) “On the Origins of the bamaNgwato.” Botswana Notes & Records Vol 5
 Mackenzie J (1871) “Ten Years North of the Orange River.” Edmonston & Douglas