Even the origins of the word "Druid" are uncertain, making it clear that this topic, while fascinating, is studied almost exclusively through secondary sources.

Word origin:
May come from Celtic word-roots 'druwid'- oak knowledge- from 'dru' meaning 'oak' and 'wid' meaning 'to know' or 'to see.'  Another possible meaning is 'great knowledge' or 'knowledge as great (old) as the oaks.'  Many scholars points out, though, that in Irish tradition, rowan and hazel are more often mentioned (in connection with the Druids) than oak. 
Irish word 'druidecht' is translated as 'magic' and 'druth' as 'fool' or 'madman' (in the sense of inspired madness or inspiration).
Sanskrit, 'drus' means 'tree' and 'duru' means 'wood.'
Lithuanian, 'derva' and 'doire' mean 'oak.'
Welsh- 'drws' means 'a door'
Gaelic- 'druidim' means 'i shut.'
Overall conclusion: The root of the word is widespread throughout the Indo-European world (as many of our earliest words were, important in indicating that it was a widespread word/knowledge, not a word that simply cropped up in a single local region).  It also had a connection with oak trees and "opening and closing of ways."  (Matthews).

When In Time:
This is a highly debated fact that has guessed ranging thousands of years and each direction.  The major theories put forth, obviously, cover just about every possible year you can pick in ancient history.
One solid piece of evidence is that Caesar said "The institution of Druids is thought to have originated in Britian, and to have become thence introduced into Gaul."  Even this early evidence notes that they are not certain of the origin of the Druids, simply that it was common myth/belief at the time that they originated in Britian. 
One can build three theories from this presumption:
1) Druids were present in Britian before the Celts arrived.
2) Druids were present in Celtic culture and came to Britian with the Celts.
3) Druids became visible after the Celts had arrived in Britian.