It seems whenever stone age people are depicted in modern culture they have wild and unmaintained hair, typically in some form of unkempt dreads. However, I know the amount of fuss that people of all different cultures put into their hair and it seems unlikely to me that people of any time would be different.
Is this simply a holdover from that pervasive idea that people of the past were savages, or does it have basis in fact?
Do we have any information about how stone age people, paleolithic or neolithic, might have styled their doos?
Nothing about the popular depiction of Stone Age "cavemen" is based in fact, because we have next to no information on things like that in prehistory. I personally agree with you that the unkempt savage look is nonsense, because paying attention to personal hygiene and appearance seems to be universal amongst the cultures we know of, and you don't need much more than some water and an occasional pass with a sharp edge to keep your hair tidy. But that's mostly speculation too.
As for hairstyles specific, what little information we do have comes from depictions of humans as figurines and, to a less extent, in cave paintings. The famous 30,000 year old Venus of Willendorf has some sort of plaited bob going on, for example (or a hat, who knows). Doug Bailey has this to say about slightly less old Neolithic figurines from Greece:
Particular parts of the body receive more attention to detail than do others. [...] Beyond the simple modelling of the cylinder and masked heads and faces, special attention was focused on realistic modelling of hair on figurine heads. On some, clay was shaped into two or three long braids (dreadlocks even) that run down the length of long, cylindrical necks. On others, the hair is parted down the middle and drawn up into a bun at the rear. Thick, full heads of hair, modelled in straight vertical tresses, frame the face of a Middle Neolithic figurine from Sesklo, though the face bears a nose so exaggerated that it is longer than the hair. On other figurines, the surface of the hair bears series of small impressions creating the appearance of a head of curly, shoulder-length locks. On other heads, hair is represented in simpler ways by diagonal sets of parallel incisions. A figurine from Pyrassos has pellets of clay on the top and rear of its head and brings to mind the similarly sized and spaced painted pattern of white dots on the red cap of the realistic Achilleion figurine. Though there is considerable variety in the ways that hair is represented in these Thessalian figurines, the common component is that hair is an appropriate element for detailed representation.^1
The take home point being that in the (surprisingly rare) instances where prehistoric peoples seem to have bothered to try and depict individual characteristics instead of abstract human forms, they made a considerable effort to get the hair right. That, and the complete absence of the archetypal caveman's shaggy mane in prehistoric art, would suggest the prehistoric people, like us, saw hair as an important component of bodily appearance. Given the variety of these depictions though, and the subjective nature of interpreting them, it's hard to say exactly what they did with it, though.
^1 Bailey 2005, Prehistoric Figurines: Representation and Corporeality in the Neolithic, p. 158
