Searches of Early English Books Online and Google Books yield six unique matches for "elbow grease" (or "elbow-grease") from the sixteenth century (including an antecedent to the one mentioned in senderle's answer, and the ones from Marvell and B.E. mentioned in Hugo's answer. Here they are, in chronological order.
From John Withals, A Dictionarie in English and Latine; Devised for the Capacity of Children, and Young Beginners (1616):
Lucernam olet. It smelleth of elbow grease.
This phrase—in the form "It smells of elbow-grease"—subsequently appears in John Clarke, Paroemiologia Anglo-Latina in Usum Scholarum Concinnata: Or proverbs English, and Latine, Methodically Disposed According to the Common-place Heads, in Erasmus His Adages (1639/1646), under the heading "Diligentia"; and again in the same form in James Howell, Paroimiographia Proverbs, or, Old Sayed Sawes & Adages in English (or the Saxon Toung), Italian, French, and Spanish, Whereunto the British for Their Great Antiquity and Weight Are Added (1659); and in John Ray, A Collection of English Proverbs Digested into a Convenient Method for the Speedy Finding Any One upon Occasion (1678) as "to smell of elbow-grease" under "Proverbial Phrases and forms of Speech that are not Entire Sentences."
From Thomas De Grey, The Compleat Horseman and Expert Ferrier (1639):
Hippophylus. What is good to helpe the heels that be scabbed?
Hipposerus. You shall many times have small dry Scabs upon your Horse heeles, which will not be greatly noxious to him, & therupon the best cure for his Keeper daily to annoynt them throughly with the oyntment made of Elbow grease. But if there be any running humour issuing from the heeles of the Horse, then let him stand every day morning and evening up to the belly in water, till the scabs do contract, then make a convenient Cautherize neer to the joynts as well crosse as thwart wise, then heale it up as you use to do kibed heeles. ✚ This is very good.
Hippophylus. Well then tell me what is good to cure the Scratches?
Hipposerus. Of this malady we have sundry sorts and degrees, unto which albeit we doe give severall names, neverthelesse they be all in effect but one and the same disease, as Mules, Kibes, Rats tayles, Crepanches, paines, &c. every of which are none other thing but the very Scratches, being certaine scabs which ingender betwixt the heele and the pasterne ioynt, and so goeth many times above the pasterne, even up to the hough, and albeit you may have this sorance sometimes upon all foure legges, yet not ordinary, for that it breedeth most commonly in the hinder legges, this is a noysome sorance, and comes sometimes through the negligence of the Groome, in that he doth not daily anoint the horse heeles with store of elbow grease, (as we tearme it) especially after journeyes and hard travell; or when he brings his horse in from water, and then doth not rub his legges and heeles dry, for that the sand and durt doth burne and fret his heeles, which doe occasion swellings, and such like swellings doe occasion the Scratches.
From Andrew Marvell, The Rehearsal Transpros'd, or, Animadversions upon a Late Book Intituled, A Preface, Shewing What Grounds There Are of Fears and Jealousies of Popery (1672):
There have been wayes found out to banish Ministers, to fine not only the People, but even the Grounds and Fields where they assembled in Conventicles, But no Art yet could prevent these seditious meetings of Letters. Two or three brawny Fellows in a Corner, with meer Ink and Elbow-grease, do more harm than an hundred Systematical Divines with their sweaty Preaching. And, which is a strange thing, the very Spunges, which one would think should rather deface and blot out the whole Book, and were anciently used to that purpose, are become now the Instruments to make things legible.
(Hugo's answer cites this same source. The wording "Ink and Elbow-grease to do more harm than an hundred Systematical Divines, with their sweaty Preaching" also appears, in italics, as an uncredited quotation in Edmund Hickeringill, Gregory, Father-Greybeard, with his Vizard Off, or, News from the Cabal in Some Reflexions upon a Late Pamphlet Entituled, The Rehearsal Transpros'd (After the Fashion That Now Obtains) (1673).)
From Robert Almond, The English Horsman and Complete Farrier Directing All Gentlemen and Others How to Breed, Feed, Ride, and Diet All Kind of Horses Whether for War, Race, or Other Service (1673):
Heel Scab, or Heels that are scabbed. Those little scabs that I have often seen growing about an Horses heels, which are more an eye-sore to the master than a trouble to himself, ingender frequently from the laziness of his keeper, and not from malignant humours, and therefore I would advise the groom or hostler to anoint them daily with Elbow-grease.
Mellet. A Mellet is a dry scab that groweth on the heel, sometimes proceeding from corruption of blood, but more commonly for want of Elbow-grease in rubbing him clean, and dressing him after he is set up wet: this Malady frequently appears like a dry chap.
Wind-galls. ... For the Cure take this Balm, which you must make thus: Take half a pound of the best Piece-grease, and having melted it, take it off, and put it into three ounces of the Oil of Spike, and one ounce of the Oil of Origanum; incorporate these together, and preserve it in a Gallipot for your use. When you have occasion to make use hereof, make it very hot and rub the Sorrance therewith, chafing it in with Elbow-grease, and to help your pains taking, hold a bar of hot Iron before the part; do thus but once in two days, though you may rub with your hand the part twice a day.
From Vincent Alsop, Melius Inquirendum, or A Sober Inquiry into the Reasonings of the Serious Inquiry: Whrein the Inquirers Cavils against the Principles, His Calumnies against the Preachings and Practices of the Von-conformists Are Examined and Reselled, and St. Augustine, the Synod of Dort, and the Articles of the Church of England in the Quinquarticular Points, Vindicated (1679):
- If some Ceremonies were abolished, because they were superstitious, and therefore dangerous, why all the rest were not served with the same sawce, that were equally, or more superstitious, and therefore more dangerous? I think it's demonstrable, that all the superstition ever stuck to Holy Water, Cream, Salt, Spittle, Oyl, was Innocency to that horrid abuse of the Sign of the Cross. But 2. if the Superstitions of the remaining Ceremonies were capable of separation from them, why might not a little Oyl and Elbow-grease have been bestowed on the rest, and their lives saved? It seems most of the Ceremonies were knocked oth' head, because they would not go to the charge of Rearing them.
And from B.E., A New Dictionary of the Terms Ancient and Modern of the Canting Crew, in Its Several Tribes of Gypsies, Beggers, Thieves, Cheats &c., with an Addition of Some Proverbs, Phrases, Figurative Speeches &c. (1690):
Elbow-grease, a derisory Term for Sweat. It will cost nothing but a little Elbow-grease; in a jeer to one that is lazy, and thinks much of his Labour.
As senderle points out in his answer. the Latin phrase Lucernam olet means "It smells of the lamp." Nevertheless, from an early date (certainly by 1616), English dictionaries translated the phrase as "It smell[s] of elbow grease." The only seventeenth-century instance of a literal translation of Lucernam olet in Early English Books Online search results is from Edward Hoby, A Counter-snarle for Ishmael Rabshacheh, a Cecropidan Lycaonite (1613):
I was euer of Demosthenes minde in this, that my writings should not onely smell of the Lampe [Lucernam olet], but if it were possible, be engrauen also in Marble [Atilan ok dunmes].
(As an aside, I hope someday to have occasion to describe someone as "a Cecropidan Lycaonite.")
The simplest explanation for this word choice is that, by 1616, the term "elbow grease" was already in fairly widespread figurative use in English for "diligent effort," and that John Withals (or those who were updating his original work) thought that the term captured the essence of the Latin phrase. It seems unlikely that "elbow grease" is simply a literal translation of a phrase used in another language.
The earliest occurrences of "elbow grease" in the course of a narrative—as opposed to as part of a phrase presented in isolation—appear in Thomas de Grey's Complete Horseman and Expert Ferrier (1639). The two instances of the expression in this book refer to "the oyntment made of Elbow grease" and "with store of elbow grease (as we tearme it)"; both can be read as playful or jocular speech, perhaps reflecting common use among grooms and other horsemen. But if "elbow grease" originated in laborers' slang, it seems a bit odd that it first appeared in print in a dictionary used to teach affluent children Latin. I don't have a satisfactory explanation for this puzzling historical record.