How did people wash dishes before dish detergent?

You mean, how did people wash dishes by hand? Same way as I usually do it now: with soap. The same bar of soap I use for washing my hands, I use for washing items by hand.

"Dish detergent" isn't really that special, if it's not for machine washing. Dishwashing machines have to use detergents very different from soap, as misguided individuals have found out from by sudsing their kitchens. But before there were machine dishwashing detergents, there were no dishwashing machines; the two grew up together, the detergents being necessitated by the machines.

But for hand dishwashing, specialized detergents are a relatively recent thing, and hardly any improvement on the all-purpose cleaners that were in general use. People used bar soap (as I still do -- try it with a dish cloth and you'll see how easy it is); if they were doing a sinkful of dishes at once, soap flakes or powder (as used for laundry). Then the same all-purpose non-soap detergent powders as for laundry, which were an improvement over soap powder for dishwashing only if you had "hard" water. The high suds products sold primarily for laundry were still labeled for washing dishes, mopping floors, etc. at least thru the 1960s, even after hand dishwashing liquids, sold as milder to hands, came into use. I wouldn't recommend the use of laundry detergents today for doing dishes by hand, since by now they're pretty specialized for laundry. But most hand dishwashing detergents haven't changed much, and may also be used for such toiletry purposes as shampoo and bubble bath -- and vice versa.

Various expedients were used for washing dishes before soap was widely available or where it was undesirable; for example, people who like a "head" on their beer avoid washing the glasses with soap or other soaplike detergents. The usual substitutes to be used with water have been alkali such as baking or washing soda -- the latter for soaking greasy dishes. Cast iron pots were, and still are, commonly wet scrubbed with abrasives.

An Account of a Strange Kind of Earth, Taken up Near Smyrna, of Which is Made Soap, together with the Way of Making It (c.1695)

From Philosophical Transactions (1683-1775), Volume 19 (free to read online).

Bringing Soap Earth employs 1000 Camels, every Day throughout the Year, or rather 1500 daily for eight Months; the four Summer Months being too hot for Camels to Travel.

An ordinary Soap House produces a thousand Dollars a year clear Profit, communibus Annis.

This article which was published in 1695 talks about the manufacture of soap in a manner which would suggest that soap was a common commodity, at least in 17th century Greece and surrounding regions (i.e. places where you would find camels for transporting it).

So I suspect that prior to the invention of modern dish detergents, people could have used regular, natural soap; and that soap has probably been around in various forms, for quite a long time.

And there are dish soaps on the market today, for people who prefer washing dishes with something more natural and environmentally friendly than detergents.

As for sponges, Greek fishermen have been harvesting natural sponges from the sea since antiquity:

The history of sponge diving in Greece dates back to antiquity. The sponge and its usage is mentioned in the Homeric epics of Iliad and Odyssey, as well as in the writings of the philosopher Aristotle. The philosopher Plato also refers to sponge as an article that was commonly used in bathing, mostly by the rich people.

And again, natural sponges are still popular with many people. In Tarpon Springs, Florida, where there is a prominent community of traditional sea sponge divers of Greek ancestry, natural sea sponges are still being harvested and sold in specialty shops.

Disclaimer: this is less an answer about the history but about the chemistry of dish washing - which I hope will serve as complementary info on some of the other answers.

I think a few points of chemical background may help understanding the historical solutions to the dishwashing question.

With the exception of burnt residue (for which mechanical/abrasive treatment is most efficient), dish washing is about cleaning carbohydrates (starch/sugar), lipids (oil, grease) and protein from the dishes.

• The carbohydrates are easiest: they are readily dissolved or emulsified by plain water, so no problem at all.

• To get rid of the lipids, you can use an emulsifier (that term really just means any substance that helps form/keep lipid droplets in water). Soaps can do this, but also e.g. lecithin (remember reading: emulsifier soy lecitin - see the soybean powder in the comment. Although I doubt that historically edible substances were used much for dish washing - but some types of food already contain sufficient emulsifier so no additional emulsifier is needed for dish washing).
  In alkaline/basic condiditons, fats (triglycerides) hydrolyze into glycerol and fatty acids which are deprotonated (anions) in the alkaline solution and thus have a hydrophilic end. These fatty acid anions act as emulsifier, so hydrolysis of a small part of the lipids is sufficient for dish washing.

• Now, proteins that stick to the dish because they are denatured by heat (frying, baking - cooking also leads to heat denaturation, but due to being in water it doesn't stick to the dish as much) are the hardest problem for dishwashing. However, you can hydrolyze also these (for practical dishwashing: sufficiently to get the remainder off mechanically). Proteins hydrolyze easily in alkaline/basic conditions, but also in acidic conditions. Acidic hydrolysis is typically slower, though. A modern alternative is using enzymes.

Thus bases do help tremendously with dish washing. Two alkaline substances that have been around for very long time are

• ashes (and their lye)
  Wikipedia says about lye soap:

  The ancient use of lye for soap-making and as a detergent is the origin of the English word, deriving from Proto-Germanic *laugo and ultimately from the Proto-Indo-European root *leue-, "to wash." Relatives in other Germanic languages, besides their words for lye, include the Scandinavian languages' words for Saturday (laugardagur, lördag, lørdag), meaning "washing day".

• and lime

  Plaster: There is archeological evidence that Pre-Pottery Neolithic B humans used limestone-based plaster for flooring and other uses.[12][13][14] Such Lime-ash floor remained in use until the late nineteenth century.

  Lime (CaO) is not so good for dish washing, because its soaps [see below] are unsoluble in water, they form scum. This is why with hard water (containing much Ca²⁺) much more soap is needed than with soft water.

• washing soda (Na2CO3) according to Wiki on dishwashing liquid was used before the modern dishwashing detergents were invented. It is the main component of natron, which was produced (among other uses also for washing and soap production) in ancient egypt.
  Sodium carbonate became cheap with the invention of first Le Blanc and then the Solvay process, so we're talking 19th century here.

Soaps are the salts of fatty acids. They are produced by hydrolyzing fat in alkaline (NaOH or KOH) solution, e.g. lye from ash. For cleaning purposes, sodium (Na) and potassium (K) soaps are used. Being a salt of a strong base (KOH, NaOH) and a weak acid, they still react basic, so for dish washing they also have the property of inducing hydrolysis of protein in addition to being emulsifier for lipids.

Others have already given citations of ancient (Mesopotamia, Egypt etc.) knowledge of soap. Let me add that until sodium carbonate became a cheap industrial product, soap was a luxury article rather than a commodity (Ullmann's encyclopedia of industrial chemistry on Soap). From that I'd guess that the every-day dish washing was not done with anything so fancy*.

Also, not so ancient history from middle Europe (great-grandma's time, anecdata): Cast iron pans were wiped, but removing grease/fat was not even intended. If they were washed to remove grease, they were greased again immediately after to prevent rusting. This meant a taste to everything that we'd nowaday refuse as rancid but which was normal in former times (compare haut-goût). Again, burnt residue was and still is best removed with mechanical means: abrasives such as sand or steel wool.
Wooden plates were rinsed but also probably not washed to be totally grease-free. (Other cultures use one-way articles like banana leaves). In general, there was more cooking (and in general more soup/stew/porridge types of food) and less frying. And cooking pots are comparably easy to clean without (much) detergent if you start immediately or let them soak.

Hard on the hands So alkaline substances help removing lipids and proteins. But in that they do not distinguish between the lipids that protect our skin and the lipids that should be washed away, nor between the food residue proteins that should be hydrolyzed and the protein of our skin. Which is why they are "hard on the hands". Modern dishwashing machine detergents do use this (possibly also enzyme-based degradation/digestion of proteins). As liquids for manual dishwashing are supposed to be in contact with exposed skin, they are neutral to slightly acidic. To achieve this, instead of soaps other tensids are used (e.g. organosulfates). This leaves the emulsifying properties, but does not help with the proteins. Instead, more mechanical action (scrubbing) plus soaking as needed are employed. Emulsifying (surfactant) properties means they still remove the lipids from your skin (excess lipids are added to toilet soaps to leave some lipid on your skin, but for dishwashing this would leave a lipid film also on the dishes).

Side note: while alkaline chemicals such as Na2CO3 or real soaps are more dangerous to the skin, they are at the same time more easily biodegradable than their more skin-friendly replacements in the manual dishwashing liquid.

In particular, after neutralizing which will often occur rather automatically as we have lots of acidic food (think fruits, wine, vinegar, sour milk etc.), all that is left is the fatty acid (as it occurs naturally during degradation or digestion of triglycerides) and the salt of, say, citric or acetic acid (also occuring naturally). So small amounts of those soaps or washing soda or ash in dishwashing water do not raise concerns for feeding the "dishwashing pig" (German: Spülsau) mentioned in @Defrance's answer.

* Little House in the Big Woods (which although it is autobiographic fiction I think can be trusted on the matter of soap use) describes 1870s settlers in the US distinguishing between the holiday use of "store soap" and homemade "slimy, soft, dark brown soap that Grandma made and kept in a big jar to use for common every day" (probably produced from wood ash and animal fat - there's also a description of using wood ash for alkaline treatment of corn/maize). But soap is mentioned only for toilet use, not for dishwashing.

My grand mother was using wood ashes from the stove mixed with water and the Dishes where finally cleaned with clean water ? then the " dirty water" was given to the pigs ! absolutely ecological !

People still often wash dishes without dish detergent. Searching for the situation in India, I found a very detailed article on the market situation:

• “The Cleaning Edge”, by Alokananda Chakraborty, February 25 1997, Business Standard

(Ignore the incorrect 2013 “last updated” date at the top; the article is from 1997 as mentioned at the end and on the author page.) The market has changed a lot since the article was written 2+ decades ago (as has society: the article frequently mentions “housewives”), but it has some revealing data on what was used (other than detergent) in 1997 in India:

a market that has barely progressed beyond rudimentary home-made scourers. Even today, almost 70 per cent of housewives prefer free-to-use proxies like charcoal, ash and even foil medicine wrappers. And among the remaining 30 per cent the penetration of branded scouring powders is very low.

[…]

Globally, the dishcare market is predominantly hand dishwash in nature. Even in other advanced markets, the penetration of dishwashing machines is as low as 10 per cent. Of course, in India, the dishwashing machine penetration is minuscule.

[…]

For one, about 70 per cent of the Indian households did not buy a separate dish scourer – they generally use proxies like charcoal, ash, mud, or even detergent powder and bars for clothes.

It also discusses different forms of dishwashing detergents, which I just discovered may not be common elsewhere:

All these different delivery forms were associated with unique benefits: the powder is associated with abrasiveness, the liquid with the attribute that it is good for the hand, and the bar which combined the benefits of both.

(And the fourth one the article discusses, which is a paste.)

On how much detergent there was even in the 30%, and the circumstances in which more was needed:

Most of the scourers in this segment had almost zero detergent content in them but sold on the plank of their abrasiveness.

[…]

The first hint that there was actually a place for another new scourer was the fact that the existing scourers could not tackle the problem of burnt vessels or stubborn grease which mirchi, haldi and other kinds of masala housewives used tended to leave behind.

[…]

myriad branded and unbranded products along with proxies like mud and ash. That was fine as long as the housewife was using copper or brass utensils. But when she graduated to more sophisticated utensils like enamelled cook-and-serve utensils and non-stick crockery, or, for that matter, glass and chinaware the need for a more sophisticated dish washing medium arose

This may also answer your question to some extent: if not using non-stick cookware, glass or porcelain, (and if you don't have much grease, and if you don't care about what happens to your or your maid's hands,) then sand/charcoal/ash/etc. will actually do.

When on a month-long kayaking trip back in the USSR, we did not bring dish detergent with us, so I have a peculiar opportunity to tell the history of soap from personal experience ;-)

You scrub dishes with sand to remove hard residue (e.g., the burned food strongly attached to the walls of the pot).

You remove fat using ash (we cooked on open fire, so ash was plentiful). You might be surprised to learn that ash+fat=soap, so it worked perfectly.

PS. Note that neither method is nice to your skin (sand is abrasive and soap is basic).