Few words, the OED informs us, have received more etymological examination than average (see the sense “average, n.2“). Ample consideration of this issue, we read, was given by eminent linguists, among whom are listed “Diez, Dozy, Littré, Wedgwood, E. Müller, Skeat, etc”. (The third one, É. Littré, is well-known in France, for his own XIXth Century French dictionary).
It seems that the mathematical sense arose from the following meanings:
2. Any charge or expense over and above the freight incurred in the shipment of goods, and payable by their owner. (In this sense it still occurs in petty average, and the now inoperative phrase, average accustomed in Bills of Lading: see quotations 1540 and 1865.)
3. spec. The expense or loss to owners, arising from damage at sea to the ship or cargo.
4. a. The incidence of any such charge, expense, or loss; esp. the equitable distribution of expense or loss, when of general incidence, among all the parties interested, in proportion to their several interests.
In this sense, it seems that “average” is directly related to the French word avarie (which, roughly, means any damage suffered by a ship or its cargo), both coming ultimately from the old Italian avaria. The OED traces the first use to 1200 (though it’s in an Old French text apparently), with English uses as far back as 1502.
In the mathematical sense, the first recorded uses seem to only come around 1750. One thing which seems to be not quite clear is whether one should say on average, or on an average, or on the average, or at an average, or something else altogether.