Perhaps the biggest challenge in answering this question is the difficulty in generalizing across space, across various kinds of nomadic groups, and indeed, across individual nomadic groups. Also, much of what can be said depends on what we know about nomadic groups in recent history and make assumptions about ancient groups. I think someone with good archeological research skills might be able to offer a more full answer for you:
Having said that, I thought I would share some observations on general aspects of nomadic trade I found useful in one article cited below:
Some groups are defined by anthropologists and historians as "pure pastoralists," that is, they are almost completely dependent upon the products they find in the lands they cover, and meat and products of the animals they bring with them. For these groups, there is very little significant trade, and it is not carried out in formalized ways. Examples include Kirghiz tribesmen. (p19) This probably corresponds most closely to the trade you are talking about before the dominance of agricultural communities.
Another way to distinguish the above group is made by E. Gellner: "symbiotic" nomads vs. "simple or primitive" isolated nomads (p42). The latter might have traded with each other but are not at the periphery of a more organized system.
Once they develop, more common was the interaction between nomadic groups and agricultural communities, as in the "symbiotic" nomads that are embedded into a larger system. Most infamously, this could take the form of raids, etc. but there was also trade in the form of barter of livestock, livestock products, and wild foods for grain, etc.
Trade between nomadic groups could take place (as pointed out by @jwenting) at appointed places. Example in the article, quoting the work of P. H. Gulliver is the Labwor Hills as a site of exchange between the Tobur and the Jie pastoralists in East Africa.(p43)
A more recent important contribution (though controversial) is the work Debt: the First 5,000 Years by anarchist anthropologist David Graeber. The descriptions of trade between nomadic groups makes frequent appearance in the work, which begins by critiquing the typical way that bartered exchanges before the existence of money are portrayed in our textbooks. Rather than an inefficient system replaced by rational accounting methods of cash, Graeber looks at the rich cultural systems of exchange, debt, and power that are embedded in these systems. Rather than telling you necessarily "where" they engaged in trade, I would encourage you to look at this source as synthesizing scholarship on how such trade was carried out and mediated relationships between groups.
Page Numbers above are from:
Rada Dyson-Hudson and Neville Dyson-Hudson
Annual Review of Anthropology
Vol. 9, (1980), pp. 15-61
Walled access at: http://www.jstor.org/stable/2155728