Additional corroboration for the "horse's teeth" origin that Avon's answer identifies:
From John Ayto, Oxford Dictionary of English Idioms, third edition (2009):
long in the tooth rather old
This phrase was originally used of horses, referring to the way their gums receded with age.
From Christine Ammer, The Facts on File Dictionary of Clichés, second edition (2006):
long in the tooth Aging or old. This unflattering term alludes to the fact that a horse's gums recede as it gets older, and transfers the same phenomenon to humankind. Th transfer understandably is not very old, since until relatively recent times adults who were old enough to experience gum recession generally had lost most of their teeth. It dates from the nineteenth century. Thackeray uses it in Henry Esmond (1852): "She was lean and yellow and long in the tooth."
From Robert Hendrickson, The Facts on File Encyclopedia of Word And Phrase Origins (1997):
long in the tooth That horses' gums recede and their teeth appear longer as they grow older, owing to their constant grinding of their food is the idea behind this ancient folk phrase, which means one is getting on in years.
Awareness of the age-related appearance of horses' teeth is also responsible for the saying "Never [or don't] look a gift horse in the mouth." Here is the discussion of that saying in J.A. Simpson, The Concise Oxford Dictionary of Proverbs (1982):
Never look a GIFT horse in the mouth. A horse's age is commonly gauged by the state of its teeth. The proverb warns against questioning the quality or use of a lucky chance or gift.
Simpson notes that this saying may be found in English found as early as Stanbridge, Vulgaria (1510): "A gyuen hors may not [be] loked in the tethe," and that St. Jerome uses essentially the same phrase in Latin in the preface to his Commentary on Epistle to the Ephesians in A.D. 420.
Nigel Rees, A Word in Your Shell-like (2004) confirms that the thing that a person may be checking when looking a gift horse in the mouth is the length of its teeth:
(to) look a gift horse in the mouth Meaning, 'to find fault with a gift or spoil an offer by inquiring too closely into it'. This proverb alludes to the fact that the age of horses is commonly assessed by the length of their teeth. If you are offered the gift of a horse, you would be ill-advised to look in its mouth. You might discover information not to your advantage.
Rees's conclusion seems a bit odd to me. The point of the expression, I think, is that any free horse is worth more than no horse at all, regardless of how long it is in the tooth—or how far it falls short of perfection—so that any vetting of the animal in front of the giver is a sign of foolish ingratitude.
Early matches for 'long in the tooth' in Google Books search results
A Google Books search finds several matches that are at least somewhat older than Henry Esmond (1852) for the phrase "long in the tooth." From Thomas Medwin, The Angler in Wales, or Days and Nights of a Sportsman, volume 2 (1836):
Though skittish, she [a mare] was only remarkable for the lowness of her action, and, what made her a favourite with her master, the consequent ease of her pace, the amble, her ordinary one. A brown gawky leggy Rozinante, very long in the tooth, and showing every bone in his skin, was generally ridden by his courier, though occasionally, by way of variety,, and to show the extent of the stud, he [the courier] was mounted on a black, entire, forest pony, who had acquired the mauvaise habitude of having his own way, and would frequently take it into his capricious head to quit the cavalcade, and return to his stable.
From Captain Bellew, "Memoirs of a Griffin," in The Asiatic Journal and Monthly Register (April 1841):
Yes, this [India] is the place for the man who wants a wife, an wishes to be met half-way, detesting, like me, the toil of wooing. There he can go, and if he sees a girl he likes, good forehand, clean about the fetlock-joints, free in her paces, sound and quiet, and not too long in the tooth, if not bespoke, he'll not find much difficulty in getting her.
The extended equating of a potential wife to a horse here is obvious. From Major Michel, Henry of Monmouth: or the Field of Agincourt, volume 1 (1841):
I tell you, dear honest David, that the squire of the most noble Earl of March is most deeply in love, and by the turn of that dear little girl's eye, I think it is reciprocal, and, forsooth, why not? We shall see : as if the old mother be sulky, why I will make love to her too, or perhaps, considering she is a little too long in the tooth for me, a friend might manage it instead.
From "The Norfolk Cob: A Celebrated Trotting Horse," in The Farmer's Magazine (October 1845):
As a stallion, perhaps the strongest proof of his excellence is the fact of his covering for fifteen seasons, in nearly the same circuit from which he was brought two years since by Mr. W. Howlett, Veterinary Surgeon, Bath, where he stood at Mr. Harvey's establishment, until the last few months, when he was purchased by Sir William Codrington, and sent out to his estates in the West Indies : rather long in the tooth, perhaps, for such a voyage, but still full of health and vigour.
And from Scribble, "My First Horse," in The Sporting Review (March 1846):
Away we went to cover ; and I had just time to see that I was on a perfect hunter, rather long in the tooth, but very short in the leg, when a hound challenged, and away went a fox for Middleton Park.
So of the earliest five Google matches, three exclusively involve actual horses, one assesses a hypothetical future wife as if she were a horse, and one is about a love interest's mother.
