Coined after the noun croque-monsieur (which denotes a toasted or fried sandwich filled with ham and cheese), croque-madame denotes a toasted or fried sandwich filled with ham and cheese and topped with a poached or fried egg.

For example, the following is from French Curb on Inflation Provokes Croissant War, published in The New York Times (New York City, New York, USA) of Thursday 10^th November 1977:

Paris, Nov. 9—Many bakeries stayed closed here this morning and most cafes put their shutters down this afternoon to protest a freeze on some food prices.
[…]
Cafes were given a ceiling price on such quick-lunch staples as croque-monsieurs, croque-madames, hot dogs and sandwiches. A croque-monsieur is ham and cheese between pieces of toast, a croque-madame the same with an egg on top. The ceiling price is 4.50 francs (90 cents) and 5 francs ($1) respectively. A few cafes have already stricken these dishes from their menus.

However, the noun croque-madame originally denoted any of various types of toasted or fried sandwich.

This variety of meanings may indicate that croque-madame was coined on various occasions by different persons, independently from each other.

The earliest occurrences of the noun croque-madame that I have found are as follows, in chronological order:

1-: From the Brooklyn Daily Eagle (Brooklyn, New York, USA) of Thursday 1^st December 1932:

A Cheese for Every Smell or Any Nose
That Is Boast of M. Androuet, ‘Master Cheeser’ of Paris, Whose Shop Is Paradise for the Cheesy, Death for the Weak
By Guy Hickok

Paris, Nov. 21—Androuet calls himself a “Master Cheeser” (Maitre Fromageur).
The window of his little shop is packed with cylindrical Stiltons from England, with “Monks’ Heads,” with Cantals as big as a Civil War drum, with Scandinavian, Dutch, Italian, German and Bulgarian cheeses.
[…]
There are Schabzeiger, Cancoilote, Gjetost, Vacherin, Collignon—and you need a strong stomach to find out what all these are. There are cheeses from Tuscany and Hungary and Belgium. There is a Croque-Monsieur au Roquefort made with toast and cooked Roquefort cheese, and a Croque-Madame Bel-Paese. It sounds cannibalistic—“Munch Mister or Mrs. with Roquefort or Bel-Paese.”

2-: From A Book of Appetizers (Los Angeles: The Ward Ritchie Press, 1958), by the U.S. chef and cookbook writer Helen Evans Brown (1904-1964):

Croque-Monsieur
This is a favorite Parisian “snack,” and don’t think that isn’t just what they now call it, though it used to be considered “une petite entrée.” […]
Croque-Madame, you may be interested to know, are the same thing except that chicken is substituted for the ham.

3-: From the Wilmington Morning Star (Wilmington, North Carolina, USA) of Friday 2^nd September 1960:

Mademoiselle, you can make a sandwich a la francais [sic]! Two sandwiches, in fact, one for the boys and one for the girls: Croque Monsieur and Croque Madame, French in name, French in origin, and French fried, these twin sandwiches, start out with white bread spread with a rich grated cheese and cream mixture. Each sandwich takes a different filling and is dipped in egg and fried just like French toast.
“His” recipe calls for a filling of sliced ham, “hers” for bacon and sliced mushrooms. The directions below are for eight sandwiches, four for mademoiselles and four for monsieurs.
16 Thin lices [sic] white bread
2 Cups (1-2 lb.) grated Swiss cheese
1-2 Cup heavy cream
4 Eggs
1-2 Cup milk
1-4 Cup butter or margariine [sic]
Trim crusts from the bread. Mix cheese and cream and spread this mixture on all bread slices, using two tablespoons per slice. Add a filling (see below) to half the bread slices; top with remaining slices, cheese side down. Now beat eggs and milk with fork. Dip sandwiches into egg mixture, coating both sides. Heat butter till bubbling in large skillet; brown sandwiches on both sides over moderate heat. (If you use electric skillet, use just half the butter—add more as you need it. Heat to 325 degress [sic] F.) Serve with knife and fork or cut into bite-size pices [sic].
Croque Monsieur: For four sandwiches, use four slices boiled ham—one slice for each sandwich.
Croque Madame: For four sandwiches, use six slices of bacon and one small can sliced mushrooms. Drain mushrooms; sprinkle with juice of one lemon. Fry bacon over moderate heat. Drain on paper towel. Use about one table spoon mushrooms and a slice and a half of the bacon to fill each sandwich.

4-: From American Food Served In French Drug Store, by the U.S. chef and cookbook writer Ida Bailey Allen (1885-1973), published in The Red Deer Advocate (Red Deer, Alberta, Canada) of Saturday 12^th November 1960:

“Now for lunch,” announced the Chef.
Into a taxi, up the Champs Elysees we careened, stopping short about a block from the Arc de Triomphe at a glittering shop with a modest sign: “The Drug Store.”
[…]
“No drug store in the world like it,” proudly commented Manager Godest.
[…]
“But, Chef, what is this, ‘Croque Monsieur’?” I asked.
“It is not like what it sounds,” laughed the Chef. “It’s a very big toasted cheese and ham sandwich for a man.
“Here is a smaller, daintier one called ‘Croque Madame’, for a lady, made with cheese and chicken.”
We ordered Normandie cider and stuffed eggs with smoked salmon and red caviar to start, then the “croques”, Madame et Monsieur.

5-: From the review, by ‘Trencherman’, of a London restaurant, published in the Marylebone Mercury (London, England) of Friday 25^th November 1960:

Trencherman, at least, is fascinated by the only savoury on the menu called “Croque Monsieur,” or “Croque Madame.” Both have grilled ham on toast for undies, but while HE has a coat of melted cheese and an olive for his head, SHE has just a skirt of fried banana.

6-: From Eating at the Fair, an article by Jack Altshul about “dining-out at the New York World’s Fair”, published in Newsday (Melville, New York, USA) of Friday 29^th May 1964:

Since France isn’t represented at the fair, I found only one little spot at which you can satisfy a hankering for authentic onion soup. That is in a bistro called Luxembourg, which seats about 20 people and is operated by a Frenchman who came here via California. He is Pierre Parker who has a Laguna Beach stand called “Lucky Pierre’s,” and at his fair diggings he is chief cook, bottlewasher, waiter and sign-painter. His onion soup goes for $2, but you can come back for seconds or thirds. If you want to wash the soup and garlic bread down with a bottle of white wine, Pierre will clip you for $6. He also serves such hot sandwiches as croque monsieur (imported ham with hot wine cheese sauce, $1.75) and croque madame (hot sliced mushrooms on French bread, $1.50).