Hey! Leila Ahmed wrote a great book, Women and Gender in Islam, and dedicates quite a lot of it to the subject of the veil. This is the primary reference that I'll be referring to for this post. I'll try and give a rough overview of how the veil developed.

---

Veiling was common in multiple pre-Islamic societies across the Middle East. In Assyrian culture wearing a veil separated between a 'respectable' woman and those who were 'up for grabs', so to say. Upper class women, concubines accompanying those women, and former "sacred prostitutes" all had to wear it whereas normal prostitutes and slaves were forbidden under threat of flogging or even having their ears cut off. Ahmed then writes that this practice spread throughout the upper-class Mediterranean world, from the Levant through to Persia, and also crossed religious lines appearing in Byzantine Christian societies. Here Ahmed gives the example of a 10th century Byzantine patriarch who wrote that he only allowed his daughter to go out "veiled and suitable chaperoned". She also notes the reasoning, separating the respectable from the rabble, remains constant even in these other societies.

However, that is not to say that veiling was necessarily widespread in Arabia itself. Women of the jahilyya pre-Islamic period did not normally don a veil. This of course varied from city to countryside, with cities being more likely to veil. Overall, nowhere was the veil common to the extent of places like neighbouring Syria and Palestine. Sexual relations in Arabia were more open than in those other societies, with both polygamy and polyandry being present.

Through Muhammad's entire life, the only women who were regularly veiled or secluded were his wives. Through successful revelations received by Muhammad, the practice of veiling and seclusion took hold among them, getting to the point where the phrasing "she took the veil" became synonymous to "she became a wife of Muhammad". Various impetuses pushed Muhammad towards these rulings. For example, it was after he became annoyed with guests staying too long chatting with his wives after dinner that the Sura 33 was revealed, within which verse 54 details that one should only speak to Muhammad's wives from behind a curtain. The word he uses for curtain is ḥijāb. Most westerners associate the word hijab with some sort of head-wrap of veil, but it also literally can mean 'veil' in the sense of a curtain. Verse 59 then gives the commandment to women to "bring down over themselves [part] of their outer garments. That is more suitable that they will be known and not be abused." This is allegedly in response to the "hypocrites", mere nominal converts to Islam, harassing Muslim women and claiming to have thought they were slaves. Finally, I should note that the later second Caliph, Omar, was a proponent of seclusion of women and veiling and actively pushed Muhammad towards this position.

So how did it spread as a practice to women other then Muhammad's wives? Ahmed states that the exact reason is unknown. It was likely to be a combination of many factors, the conquest of areas such as the Levant where veiling was a more common practice, increases in wealth leading to more of a division between the 'respectable' women and others, and the imitation of Muhammad's own wives. Sorry I can't give too much more information on this aspect of the question at the moment, but I've currently not quite got the time to do more digging.

In any case, I hope this gives at least an overview of the early history of the veil. If you have any questions, please ask!