My wife and I like to play games like Paper Mario together. Paper Mario is a long game with a lot of dialog. At any point in the game, you can talk to any character, and that character will say something "sensible". For instance, they'll ask you to help them out, or they'll thank you if you've already helped them out. I've always wondered how that's coded. Similarly, I've always wondered how many ways I could think up to code it.
The simplest approach is to use a complicated set of possibly nested if/else statements. For instance, if Mario has this item, then say this. Otherwise, if he has beaten this level, say that. Certainly that's a valid approach, and it doesn't even matter if it's slow. Since people read so slowly, trying to optimize how quickly you can come up with what text to show next is absolutely the last thing you would ever need to optimize in a video game.
At the opposite extreme, this problem could be solved with a rules engines. There are libraries that let you wrangle control of complex if/else hierarchies. (The first time I heard about rules engines was when I was interviewing at a consulting company where they were building a welfare system for various counties in California. Apparently, the rules surrounding welfare systems are so complex that a rules engine is a necessity.)
You can also use a mix of if/else statements and switch statements. For instance, the main game is a mostly linear progression from one state to the next, which is easily solved by a switch statement. If you are in this state, say this. If you're in that state, say that. However, sometimes Mario goes on side quests. In cases like that, a particular character might need to have a separate switch statement to know what to say for that side quest.
Similar to using a switch statement, you can use a non-sparse array per character where each state is an index into that array, and each spot in that array has a pointer to a message. Since the array contains every state, many of the states will point to the same message.
You can create a mapping from state to message using a sparse tree. To find out what to say, traverse the tree to find the state that is closest to, but still less than the current state. A sparse tree has a benefit over a non-sparse array in that the tree is only as large as the number of messages the character might say.
Rather than having an array of states for each character, you could also have a single array of states for the entire game. When you save the player's position in the game, you simply save his index into the array. The first spot in the array has a mapping of what every character would say at the beginning of the game. Each new spot in the array has a list of updates for all the characters who would say something different for that new state. This works like a database transaction log. Since there are only a few hundred or a few thousand characters, you can easily store in memory what each character would say at the current state in the game.
I'm going to take a guess and say that they probably just used a simple set of nested if/else statements, but it's kind of fun to think of other approaches.