My basic advice is: start from what they know.
For example, in some languages, you need to choose different personal pronouns depending on whether they are used as a subject or as an (direct/indirect) object:
"He" (subject) becomes "him" (direct object).
"He" (subject) becomes "him" (indirect object).
Using this as a starting point, you can then explain that in many languages (e.g. Polish, German, Icelandic, Latin, ...), this change also applies to other categories of words, e.g. nouns and articles:
- Der Hund hat den Mann gebissen. (The dog bit the man.)
- Der Mann hat den Hund gebissen. (The man bit the dog.)
You can then add adjectives:
- Der hungrige Mann hat den Hund gebissen.
- Der Hund hat den hungrigen Mann gebissen.
Finally, you can add that prepositions require specific cases (e.g. German prepositions requiring the nominative, dative or genitive case) and that verbs may require cases that you don't expect (e.g. German cases with the genitive, such as "gedenken").
If you're starting from a language that has no morphology, e.g. Standard Chinese, you need to start from word order and how word order determines the function of phrases in a sentence. For example, in Chinese, you can start from the difference in meaning between:
- 她爱我。(She loves me.)
- 我爱她。(I love her.)
In the above sentences, how do you know who is loved by whom? From the word order. You then go on to explain that other languages modify the words to indicate who is the subject and who is the object of the action. Once this is understood, you can move on to the steps at the start of this answer.