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:
http://ilorentz.org/beenakker/MO/normalis.png
"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?).