How did "normal" come to mean "perpendicular"? How and when did the word "normal" acquire this meaning? When I first thought of this, I couldn't really come up with any explanation that wasn't complete speculation -- pretty much all I was able to see was that it isn't any stranger than "right" in "right angle" -- the angle is probably as right as the lines are normal. But on reading the etymology note in the entry for "normal" in the American Heritage Dictionary,

Middle English, from Late Latin normalis, from Latin, made according to the square, from norma, carpenter's square;

I thought that was probably it -- it probably came from the perpendicular sides of a carpenter's square. Did it then? And how was it introduced? If this is indeed what's going on, either the meaning must have been introduced long ago, when people still realized what the etymology of "normal" is, or some really erudite mathematician must have introduced it, perhaps to show off their erudition.
So how did it happen?
 A: normalis already meant right-angled in classical Latin; for example, angulus normalis appears in the first century text De institutione oratoria (volume XI, paragraph 3.141) by Marcus Fabius Quintilianus. 
In a commentary on this text from the fifteenth century this early use of the word "normalis" is explained as "rectus", see screenshot:

"Angulus normalis est idem qui angulus rectus" = "a normal angle is the same as a right angle"

In response to Ketil Tveiten's question: "How did normal come to mean ordinary" : according to this source, the meaning of normal as conforming to common standards seems to be of recent origin (1828?). 
A: I addition to what has been said I would also like to point out that Geometry began as a tool for construction. When building, almost all corners are right angles. In other words a 'standard' corner is a right angle. When you think of it in these terms the common usage of the word normal is a metaphor. For example, "I normally get chocolate ice cream" could be phrased "I build walls at right angles with about the same frequency as I choose chocolate ice cream".
A: Perhaps it should be mentioned that while normalis did mean perpendicular in classical Latin, it was not the only possible (and perhaps not the preferred) choice of words.
I asked about expressing perpendicularity in classical Latin at the new Latin Language SE site.
The answer given there lists a number of expressions, mainly from Vitruvius:


*

*πρὸς ὀρθᾶς — yes, this Greek expression was used in Latin.

*ad normam — according to norma, a square employed by carpenters, masons, etc., for making right angles.

*ad perpendiculum — according to perpendiculum, a plumb-line

*ad perpendiculum et normam — combination of the previous two

*directus — "straight", essentially the same as rectus used in the medieval commentary Carlo mentions


There is a finite amount of extant Latin literature and perpendicularity is not the most common of subjects, so it is difficult to tell what exactly are the differences between these phrases in usage or frequency.
The examples listed above, apart from directus, mean "orthogonally".
For the adjective "orthogonal" one might use directus, rectus or indeed normalis.
Vitruvius does not use the word normalis at all.
Notice that norma and perpendiculum are two different tools used to create straight angles, not geometrical descriptions of the angle itself.
I am not aware of any ancient mathematical texts in Latin, either original or translations.
It would be interesting to see which expression would be chosen in mathematical context.
If you know any suitable sources, consider answering "Where to find ancient mathematics in Latin?".
(The phrase mentioned in Carlo's answer can be found in the Perseus service together with an English translation in a more readable and searchable form.)
