Several Neanderthal skeletons have been analyzed to see whether their bodies showed evidence of spear thrusting and throwing (this could help us understand prehistoric tool use and hunting practices). They were found to have bilateral asymmetry between their right and left humeri (upper arm bones). On the skeletons analyzed, one humerus had an oval cross-section while the other had a rounder cross-section. The oval shape resulted from repeated flexing stress to the humerus, and experiments with two-handed spears made it clear that these are the kinds of stresses you experience on the hand that holds the back of the spear and generates the thrusting force. The bones on one side of the body (but not both) changed shape because of repeated stresses through the person's lifetime -- ie, they always thrust their spears using the same hand on the back end of the spear shaft.

That means these people were not ambidextrous. They had a favorite hand, and they used it more than they used their less favorite hand.

So yes: handedness goes way back into prehistory!