*Anthropologist hat on* I love these snazzy hats!
The Stone Age is actually divided into three periods, based on the types of tools and the relative complexity of society. The reason it's called the Stone Age is because of the preponderance of stone tools among surviving artifacts, as they also used bone, antler, wood and there is evidence of rope and fabric.
The Paleolithic is from the dawn of tool use (predating Homo Sapiens, I might add, Homo Habilis and Erectus were the source for the earliest and most primitive stone tool traditions). Here we see very primitive and basic tools, albeit of a rather broad variety at first although later it seems to narrow down to the Swiss Army Knife of the Paleolithic, the Handaxe (seriously, with a handaxe you can chop, cut, drill, bash, saw... very clever tools that were in use for over a million years)
Then you have the rather nebulous and transitory Mesolithic, which is when you start to see the earliest examples of agriculture starting, along with more elaborate construction and tools. It's very difficult to identify Mesolithic artifacts because the stone tech is nearly identical to Paleolithic, the difference is primitive agriculture. You usually need surrounding context at the site to make the identification.
Then comes the true Agricultural Revolution and the Neolithic. Tools become much more sophisticated, with a larger proportion of obsidian blades and such, tool making techniques become exceptionally refined (with some surviving artifacts being damn near works of art). You also see the first evidence for mass domestication, the first dogs, larger permanent settlements, and rapidly increasing complexity. The variety of tools explodes, and you also start finding large amounts of pottery shards (seriously, potsherds are the single most common discovery in an archaeological site by a rather massive margin, and the distinctive characteristics of them are used to identify many of the neolithic cultures)
Neolithic cultures could be extremely sophisticated in terms of their projects and such. There are Neolithic cities in India that housed upwards of 100,000 people for example. You have massive agricultural works (terracing, irrigation, etc), you have monumental architecture, you have evidence of trade networks that spanned continents from this period. (Finding a Corded Ware potsherd in the Mideast, for example).