Eva has given good definitions. I'll try to illustrate with examples.
Stereotype: [please note that this may have a grain or two of truth to it!] An American tourist, wearing shorts and a multi-colored shirt, talking very loudly to a local person in some European country.
Another: A politician [pick the country of your choice], using many big words, making promises no mortal could keep.
A cliche is a trite remark, which when first used was original, but has become stale through overuse: