For example, you wouldn’t use girl for a 40 years old woman or kid for a 20 years old woman (unless you’re far older).
Fräulein for single woman between what ages?
What is the age range for Mädchen?
Fräulein is not typically used any more. In fact, a lot of women can become quite upset if addressed this way. (Quite some time ago it described an unmarried woman, completely independent of her age).
You would use Mädchen for children and every time you wish to point to the fact that they are minors. After that, it would either be junge Frau or simply Frau.
Please note that the transition from Mädchen to Frau is a very soft one. In an official context, you would not use Mädchen for a woman of 18 years or more. In a more colloquial setup, that can be extended, and in a private context, there is no age limit for Mädchen.
The former german chancellor, Helmut Kohl, used to call Angela Merkel Mein Mädchen, which was supposed to express that he was fond of her, and on quite friendly terms. Angela Merkel at the time was well in her thirties.
It can also transport the age difference.
Again, note that someone has to be quite close for this word usage.
»Das Mädchen« is the historical diminutive of »Die Maid«. »Die Maid« has the same etymologic root as the english word »the maiden« and has a very similar meaning. A Maid was a young woman, often meant as sexually mature, but still being a virgin. A small (younger) Maid was a Maid-chen, which was always written as Mädchen.
So, a Mädchen is a female child. But when time passed by, the word Maid was used less frequently, and Mädchen began to be used in the same meaning as Maid before. In the 1970’s Mädchen was the usual word for women younger than 25 or 30 in a non-official context (among friends, but not in the job or in a shop or office).
But things changed again. Young women wanted to be respected in the same way as men of the same age. So, they didn’t want to be called »Mädchen« when they were physically mature women.
Nowadays it is safe to call a girl younger than 13 a »Mädchen«. If a woman is older then 18 or 20, then only her boyfriend/partner/husband might call her »Mädchen« (and only if she likes to be called so). So, as rule of thumb: When you can guess, that she is older than 14 or 15, avoid to call her »Mädchen«. She will like to be called »junge Frau« or just »Frau«.
»Das Fräulein« is also a diminutive. It literally means »small woman« or »little woman«. When the word »Maid« began to disappear, it was replaced from the younger end of its meaning-spectrum by »Mädchen«, as described above, but also from its older end by »Fräulein«. When the Maid has gone completely, »Mädchen« and »Fräulein« overlapped.
»Fräulein« was extensively used between 1850 and 1950, and had a more serious and mature touch than »Mädchen«. When ever a young tough woman was working and earning money (which was unusual in those days), she was called »Fräulein«. (The »Fräulein vom Amt« was the young lady who manually connected lines for phone calls, and a young female teacher was »das Fräulein Lehrerin«)
This is, why »Fräulein« became a synonym for the waitresses in a café or restaurant. This synonym is so branded in the German speaking society, that many people even in 2015 don’t know how to call a female waiter other than »Fräulein«, which is a problem, because »Fräulein« nowadays is considered political incorrect.
When ever »Fräulein« was used for children, then in one of two meanings, both somehow ironic:
Oh, du bist heute aber schon ein richtig großes Fräulein in dem schönen Kleid!
Na, mein Fräulein, habe ich dir das erlaubt?
But since »Fräulein« is a diminutive whose meaning can be interpreted as »a woman, but not for 100 %«, young women began to dislike it even more than »Mädchen«. And nowadays the usage of »Fräulein« is considered political incorrect. You better never use this word.
»Das Weib« never was used for girls or young women, always for mature women only. In days, long ago, German had this two pairs of words of adult people of different gender:
The first pair was used when the topic was the being and behavior as human creature (eating and drinking, sleeping, and of course sexuality). And when ever the differences was pointed out (der starke Mann — the strong man; das verführerische Weib — the seductive woman) this pair was used. And for that reason we still have this pair of adjectives:
männlich — weiblich (male — female)
The second pair (Herr–Frau) was used in a more sophisticated and cultural context. We still use this pair in salutations and addresses:
Frau Martha Eisenstädter
Herr Josef Steiner
But in 16th century in aristocratic societies the french word dame (french »dame« = mistress, woman, wife) was imported into German vocabulary, and over the centuries it changed the pairs:
This happened hand in hand with the devaluation of »Weib«.
If you want to refer to a women older than 15 or 18, then »Frau« is almost always the best choice. It is not a grammatical neuter diminutive like »Mädchen« or »Fräulein«, and it has not this somehow eccentric and uppish aura that sometimes is around the word »Dame«.
Mädchen will usually emphasize the young age (< 18) of the person. It may also be used expressing fondness. It is also used in the context of fashion models. (cf. girl)
Fräulein is deprecated. It was used for unmarried women, which means you are inferring a maritial status, which might be offending. It was also used for waitresses, stewardesses, receptionists etc, implying they were not married. It sounds almost despective nowadays. (cf. Miss)
Dame is a formal way to refer to somebody. It is very respectful and in my opinion the word of choice in public space when referring to and/or talking to somebody you don’t know. “Meine Dame” can be used to address somebody but it sounds a little old-fashioned. Addressing a group of people, e.g. in a speech or letter, it is commonly used in the phrase "Meine Damen und Herren" resp. "Sehr geehrte Damen und Herren" (cf. lady, Madame)
Frau is a neutral way of referring to an adult or close-to-adult woman (> 16, maybe > 14, depending on the context). It is also used to address sombody formally appending the last name. (cf. woman, Ms)
If you are asking for referral to third persons, (‘the woman I met this morning’) the general terms you want to be aware of are:
Mädchen (and its dialectal forms like Madl, Mädel, etc.)
Mädchen works as long as the person can be considered a child or (young) teen, i.e. you would address them using du. (The overlap is not perfect but close enough.)†
Dame when used outside of certain special environments,‡ would be used exclusively when referring to elderly women with grey (or white) hair and at least a walking stick.♦
Frau would be used for everything else.♠
Do not use Fräulein unless you are prepared for the shitstorm that will follow. It is no longer considered adequate.
†: Note that the dialectal forms, especially Madl (Bavarian) can be used for young adults, too. Referring to grown women as Mädchen can be understood as anything between belittling and affection (cf the various references on this page to Helmut Kohl’s Mädchen Angela Merkel). I use Madl for all my female friends even if they are well in their twenties.
‡: In service environments, e.g. higher class restaurants, Dame and Herr may exclusively be used instead of Frau and Mann signifying the higher class as highlighted e.g. in Hubert’s answer.
♦: You can put your foot in it by using the word too liberally. I was once told off for using Dame referring to a woman who clearly felt younger than she looked (although she did fulfil the criteria of walking stick and grey hair).
♠: Note that Frau is never wrong for people older than Mädchen. specifically, it is always okay to refer to very old women as Frau. See also the note above.