A calque of the French phrase armé jusqu’aux dents, armed to the teeth means formidably armed. (Likewise, the lion’s share is a calque of the French phrase le partage du lion.)

The image is of a combatant with a knife or a dagger between his teeth and another weapon in his hands.

This phrase is first recorded, in the form armed up to the very teeth, in the Fourth Volume (London, 1735) of The History and Adventures of Gil Blas of Santillane:

We set out at last from Madrid, one fine Morning at Sun-rise, and took the Road to Cuenca; observe in what Order, and with what Equipage. My Confidant and I were in a Chaise drawn by two Mules, and driven by a Postilion; three He-Mules laden with our Cloaths and Money, and led by two Grooms, followed immediately after; then came two stout Footmen, chosen by Scipio, mounted likewise upon two Mules, and armed up to the very Teeth: The Grooms likewise had Hangers by their Sides, and the Postilion had a Pair of good Pistols at the Pommel of his Saddle.

This book is an anonymous translation of Tome IV (Paris, 1735) of Histoire de Gil Blas de Santillane, a picaresque novel (1715 to 1735) by the French playwright and novelist Alain-René Lesage (1668-1747). The original French text is as follows:

Nous partîmes enfin de Madrid un beau jour au lever de l’Aurore, & nous prîmes la route de Cuença ; voici dans quel ordre & dans quel équipage : Nous étions mon confident & moi dans une chaise tirée par deux mules conduites par un Postillon ; trois mulets chargés de nos hardes & de notre argent, & menés par deux Palfreniers, nous suivoient immédiatement ; & deux grands Laquais, choisis par Scipion, venoient ensuite montés sur deux mules & armés jusqu’aux dents : les Palfreniers de leur côté portoient des sabres, & le Postillon avoit deux bons pistolets à l’arçon de sa selle.

The current form of the phrase appeared in the translation (London, 1749) by the Scottish author Tobias George Smollett (1721-71) of Tome IV of Histoire de Gil Blas de Santillane:

from Volume IV of The Adventures of Gil Blas of Santillane (2^nd edition – London, 1761):
At length, we set out from Madrid early one morning, and took the road to Cuença, in the following order and equipage: my confident and I were mounted in a chaise and pair, conducted by a postilion; three moyles loaded with our baggage and money, and led by two grooms, followed close after; and two lusty lacqueys, chosen by Scipio, mounted on mules, and armed to the teeth, brought up the rear; the grooms wore sabres, and the postilion had two good pistols at his saddle-bow.

The French phrase armé jusqu’aux dents is first recorded in La Trésorière (first performed on 5^th February 1558, Julian calendar), a comedy by the French playwright Jacques Grévin (1538-70):

from Les Poètes françois, depuis le XII^e siècle jusqu’à Malherbe (Volume 5 – Paris, 1824):
Ils sont armez jusques aux dens,
Et si chascun son baston porte.
[They are armed to the teeth,
And thus each his stick carries.]

The French novelist and short-story writer Guy de Maupassant (1850-93) used the variant armé jusqu’aux cheveux, armed to the hair, in L’Aventure de Walter Schnaffs, first published in Le Gaulois (Paris) of 11^th April 1883:

En un instant cinquante soldats, armés jusqu’aux cheveux, bondirent dans la cuisine où reposait pacifiquement Walter Schnaffs.
[In an instant fifty soldiers, armed to the hair, leapt into the kitchen where Walter Schnaffs was peacefully lying.]

I have found another early instance of the English phrase, in the form armed to the very teeth, in Volume the Third of Memoirs of the Baron de Tott, on the Turks and Tartars. Translated from the French by an English Gentleman at Paris, under the immediate Inspection of the Baron, published in The Pennsylvania Packet, and Daily Advertiser (Philadelphia, Pennsylvania) of Wednesday 10^th December 1788:

These Asiatics, dispersed throughout the capital, armed to the very teeth, lying in wait night and day, in the streets, to rob the passengers*, hastened the negociations, from the urgent necessity there was of freeing the capital from such a banditti.

(* Here, passenger is used in the obsolete sense of passer-by.)

The original French text is as follows in the Third Part of Mémoires du baron de Tott, sur les Turcs et les Tartares (Amsterdam, 1784), by the French military officer and diplomat François, baron de Tott (1733-93):

Ces Asiatiques répandus dans la Capitale, armés jusqu’aux dents, embusqués soir & matin dans les carrefours en y détroussant les passans, accéléraient la négociation par la nécessité urgente de se débarrasser d’une pareille canaille.