The term greasy spoon denotes a dingy restaurant that serves cheap food. (The term dirty spoon also had this signification.)

The earliest occurrence of greasy spoon in the Oxford English Dictionary (2^nd edition, 1989) is from Idioms of the Road and Pave, by Randolph Jordan, published in The Writer’s Monthly (The Home Correspondence School – Springfield, Massachusetts, USA) of June 1925:

Greasy spoon, a low~class restaurant.

However, the term greasy spoon is older, and, with one exception [cf. footnote], all the earliest instances of this term that I have found are—to some extent or another—associated with German speakers.

The very first of those instances occurs—apparently as a translation from German—in The Times (London, England) of Tuesday 3^rd September 1850, which published a correspondence from Rendsburg, a town in the Duchy of Holstein (in present-time northern Germany). The context is a military conflict between Denmark and Prussia on the issue of sovereignty over the Duchies of Schleswig and Holstein. After explaining that “the Holstein Government [had] advertised in all the journals throughout Germany for volunteer officers”, The Times’s correspondent wrote:

With the officers seeking service, and it may be added those actually serving, the Rendsburg inns are a subject of grievous complaint. The proprietors do not bate a skilling¹ from their reckonings, even to the most patriotic of Germans; on the contrary, they are making use of the opportunity and extort all they can for the most villainous kind of food and lodging. There are but two houses that assume the name of hotels, one very bad, and the other a great deal worse. On the latter the officers have bestowed the name of “the greasy spoon,” the constant state of this article being taken to indicate the condition of everything else. Here the military dine and grumble daily, but can effect no improvement. In all things necessary to good living the place abounds. Meat, bread, and vegetables are all good, but lack of skill and carelessness spoil them all, chiefly from sheer want of cleanliness. A Calmuck² tent could not furnish more filthy messes than are served up here daily, and which are charged at the rate of the luxuries of Hamburgh and Berlin. There is no remedy but to accommodate yourself to circumstances—fish the dead flies out of the soup, keep to windward of the rôti, and make the best dinner you can.

¹ A borrowing from Danish, the German noun Skilling corresponds to English shilling.
² Calmuck is a variant spelling of Kalmuck, designating a member of a Mongolian people living on the north-west shores of the Caspian Sea.

With one exception [cf. footnote], the other early instances of greasy spoon that I have found occur:
– in 1891 and in 1898;
– in newspapers published in Minnesota, USA;
– as proper names given to specific eating-places.

1: In The Minneapolis Tribune of Thursday 30^th July 1891. The man with the “great advertising scheme” is apparently a German-American:

A GREAT SCHEME.

“There’s been a man waiting around here to see you all day,” said Exposition Manager Brackett to Press Agent Woodward yesterday afternoon.
“What did he want?” asked the press agent.
“He had a great advertising scheme for you,” replied the manager. “Hello, here he comes back now!”
A very seedy looking individual, wearing a dilapidated-looking silk hat, and over whose face a cloud of dejection hovered, entered the office.
“Sa-ay, I’ve got a scheme fur yer life,” he said enthusiastically, “one wot’ll bring in all der trade in de hull country.” He proceeded to explain as follows: “Its somethin’ as ’ll make people look. Dat’s de principle of advertisin’. I used to be advertisin’ agent fur de Greasy Spoon restaurant in St. Louey. I used ter walk aroun’ an’ carry a banner wid de bill of fare on it. Sometimes I used ter carry de banner nights too—, but I’m digressin’. Dis scheme is fur me ter get a permit from Tom Lowry ter ride on top er de street cars. You can rig one out in green satin er some such like color, an’ I’ll holler to der people all ’bout der expersishun. Dat ’ll fetch ’em. Yer could git lots er fellers to ride on de odder cars an’ do de same ting. Wot do yer tink er de scheme?”
He seemed greatly pained at the lack of enthusiasm.
“I hardly think that idea would be practical,” said the manager.
“I think it would draw a crowd,” replied the press agent.
“Will yer gimme der job?” he asked anxiously.
“I’m afraid we cannot,” replied the manager.
“Well, den I’ll tell yer wot I’ll do. Yer gimme er quarter fur de idee—see?”
But he was compelled to seek another market for his wares. As he walked away he said, threateningly: “I’ll put some er dem St. Paul fellers on ter der snap.”
Such is the life of an exposition manager.

2: In a story published in The St. Paul Globe (St. Paul, Minnesota) of Friday 29^th April 1898. Written forms such as das (a German definite article) and maister (for German Meister, meaning master) indicate that the customer is a German speaker:

A person who was not long over from foreign parts went into a restaurant, the sign of the “Greasy Spoon,” on Seventh street, late Wednesday night and asked for a dish of ham and eggs. He was not au courant with the American bill of fare and its possibilities, and ham and eggs were the limit of gastronomical possibilities with him.
The dish was presently set before him, and he looked about for something wherewith to spice his food. He got his eye on the Tabasco sauce bottle. It looked as though it might do a dish of ham and eggs some good; add some little relish to the eggs and make the ham more savory. He probably thought it was tomato catsup, and he carefully unscrewed the top from the bottle and poured a liberal libation on one of the eggs. Then he carefully lifted that egg on the blade of his knife and gave an exhibition of sword and egg swallowing that did his trainer proud.
The instant after he had successfully performed the feat there came over his face an expression of horror; he grasped his vest with much violence; he strained his neck and the cords stood out on his forehead. He reached over and got the water glass and drained it. That gave the Tabasco the only thing it lacked—distribution. He gave an awful yell, rushed to the water cooler and turned it up over his head. When he finally got his breath he ejaculated:
“Aye shall not eat das aig; aye not bin a hot anuf feller to eat aigs vit cayeene ketchup. Say, maister, you got some stock-fisk soaked in cold water?”

3: In the issue of Wednesday 13^th July 1898 of the same newspaper, i.e. The St. Paul Globe (St. Paul, Minnesota)—and perhaps about the same restaurant that this newspaper had mentioned on 29^th April. The written forms dat for that, de for the and dem for them seem to transcribe characteristics of a German accent:

“Say,” said the night waiter at the Sign of the Greasy Spoon to the man who was waiting disconsolately for his pork and beans, “say, did you hear dat Henry Bahe was goin’ ter be de main pipe nights over at de station? Di you hear anyt’ing about it?” The victim responded listlessly that he had not heard, that he didn’t care, that Mr. Bahe might be the main pipe at the bottom of Lake Phalen for all he cared.
“Well, I’d like to see Henry land,” said the waiter. “He knows how ter eat, he does. De first time he come in here he knocked a twister in me. He h’ists himself on dat stool an’ he sings out ‘Fry me two dozen eggs, straight up an’ well done.’ I thought he was kiddin’ me an’ I asks him if he wants to carry them all home and at once he tells me not to get gay but go and fry eggs. An’ may I never pilot another dish to de counter if he don’t scoff dem all. Now he comes in regular and gets a couple of dozen fried or a dozen an’ a half scrambled. A guy that can eat like that can carry my money, an’ I hope Henry will land.” Which goes to show that popularity with the masses may not always be the result of a great mentality. A capacity for eggs helps some.

 

Note: No German speaker is mentioned in the following from The St. Louis Republic (St. Louis, Missouri, USA) of Tuesday 24^th August 1897, in which greasy spoon is the proper name of a saloon, i.e., of a place where alcoholic drinks may be bought and drunk:

A CUT-RATE WAR HAS BROKEN OUT.
WARRING SALOONS ON THE LEVEE REDUCED THE PRICE OF A DRINK OF WHISKY.
“Two and a Half Cents a Drink, and You Can Pour It Yourself.”

A cut-rate war has broken out on the Levee, and the Weary Willie who is fortunate enough to have a nickel concealed about his person is now a capitalist. That nickel will buy two drinks of whisky, and the roustabouts who are troubled with a horrible thirst, and most of them have this, are accordingly happy in consequence.
For years the nickel has been the unit of finance in the cheap saloons on that delectable thoroughfare. With it the thirsty and hungry ones could purchase a schooner with a free lunch thrown in, or a deadly dose of “pure Kentucky whisky fresh from the still.”
The happiness of the roustabouts is caused by the cut-rate war which was inaugurated yesterday. Two saloons are “bucking” each other, and the result is that the price of whisky has gone down to three cents a glass or two glasses for a nickel. The fight was started about noon yesterday by a saloon which is known to the roustabouts by the euphonious title of “The Greasy Spoon.” The saloon bears no sign of any description over its door, yet the Greasy Spoon is well known to all the deckhands on the river. The proprietor of this thirst emporium was standing in his doorway about noon yesterday, and the sight of a crowd of Levee habitues entering a rival saloon a few doors away caused him to tumble to the fact that he would be compelled to get a hustle on or this rival would get all the trade.
A short time later a sign, rudely painted, was hung in the window of the Greasy Spoon. The wayfarers who stopped to read it saw that it blazoned forth to the world at large and Levee roustabouts in particular that good whisky could be purchased there for the consideration of 4 cents per drink. The news flew like wild-fire, and in a few minutes the Greasy Spoon was doing a rushing business. The proprietor of the rival saloon went out on a prospecting tour to discover the cause of his sudden loss of customers. He saw the sign in the window of the Greasy Spoon, and the crowd making merry inside. A short time later he had cut the price to 3 cents a drink, and hung out a sign to that effect.
This brought him back the trade and the proprietor of the Greasy Spoon was forced to meet the cut. Things were about equal after this, but the rival saloon man was not satisfied yet, so he announced a further cut of ½ cent per drink. Whisky could now be purchased at the rate of two drinks for a nickel. The Greasy Spoon met this cut and dealt his opponent a stunning blow by breaking one of the time-honored customs of the cheap Levee saloons. As far back as the time the price of a drink was made 5 cents it has been the custom of the purchaser to hold the glass while the bartender poured out the drink.
This rule the proprietor of the Greasy Spoon fractured, by announcing that hereafter each drinker would be allowed the privilege of pouring out his own drink. This was a winner, and the Greasy Spoon was on top. The matter stood that way when business on the Levee closed last night. There was considerable talk last night of the proprietors of the warring saloons getting together this morning and effecting a compromise, which will result in the restoration of rates.