Rabbinic writings (e.g. * Rabbah and other midrash) use the words "mashal" (noun) and "nimshal" (verb). What do these terms mean in English? I've heard "parable" or "allegory" for the noun but I am very uncertain about "nimshal". How should I understand these words when I encounter them in this context?
Mashal= Parable. It is a story or comparison for the sake of conveying a deeper truth.
Nimshal= Technically it means moral. It is the deeper truth being hinted at in the story.
For instance in Aesop's fables, like the tortoise and the hare, in which a bullying hare is challenged to a race by a tortoise. The hare takes off, and confident of victory naps, the tortoise though tired continues to plug on, and when the hare awakes he sees the plucky tortoise win. The Nimshal, is 'many people have good natural abilities which are ruined by idleness; on the other hand, sobriety, zeal and perseverance can prevail over indolence. Source.
Oh on a gramatical note. משל is both a noun and a verb in the Paal(or Qal depending on how scholarly you want to be) form. While נמשל is also both a noun and a verb in the Niphal. The diference being that the Paal is active/stative while the Nifal is passive/reflexive. Source.
"nimshal" means something like "to be compared with" or "to be like".
It's also used in a general sense as the lesson learned from the "mashal".
I'll add that "nimshal" isn't commonly used in modern Hebrew, and many people don't know the difference between the two.
Mashal is, as you say, the story which is trying to teach a lesson
The nimshal is the lesson which that story teaches--the moral of the story.