Etymonline.com says the meaning of making somebody self-conscious is first recorded in 1828 and shows a French and Italian origin:
1670s, "perplex, throw into doubt," from Fr. embarrasser (16c.), lit. "to block," from embarras "obstacle," from It. imbarrazzo, from imbarrare "to bar," from in- "into, upon" (see in- (2)) + V.L. *barra "bar." Meaning "hamper, hinder" is from 1680s. Meaning "make (someone) feel awkward" first recorded 1828. Original sense preserved in embarras de richesse (1751), from French (1726): the condition of having more wealth than one knows what to do with.
The OED says the etymology is from "French embarrasser, lit. ‘to block, obstruct’, < embarras" and their first quotation for making someone feel awkward is from Webster's 1828 An American dictionary of the English language.
Here's Webster from 1828 (plain text):
Q: and how did it come to have the meaning of making somebody self-conscious and abashed?
It originally meant to literally encumber, to hamper or to impede; or to perplex, to confuse. It later then came to the modern meaning, as in OED's definition 2.b.:
To make (a person) feel awkward or ashamed, esp. by one's speech or actions; to cause (someone) embarrassment.
So one's speech or actions are stopping and perplexing the other, which causes the feeling of awkwardness.
Here's some examples from the introduction to Webster's 1828 dictionary that show the different meanings:
I found myself embarrassed, at every step, for want of a knowledge of the origin of words
Similar contractions have taken place in all other languages; a circum-
stance that embarrasses the philologist and lexicographer at every step of his
researches; and which has led to innumerable mistakes in Etymology.
Lexicographers are often embarrassed to account for the different signifi-
cation of words that are evidently derived from the same root.
This practice of blending with the English many words of an orthography, which in our language is anomalous, is very embarrassing to readers who know only their vernacular tongue, and often introduces an odious difference between the pronunciation of different
classes of people
On the other hand, all that I have seen, serve only to obscure and embarrass
the subject, by substituting new arrangements and new terms, which are as incorrect as the old ones, and less intelligible.