Emily Short has written a great deal of very important stuff on this topic. Have a look
here and elsewhere on her website. This is specifically about how to do conversation in the context of Interactive Fiction (i.e., text games), but the principles are the same.
The fundamental question, really, is whether you want a system of pre-programmed questions and responses, or one where characters actually construct their own dialogue. The former is obviously simpler and more traditional, and will usually be implemented as a "tree" - although of course such trees can be very complex if you take the time to make them so. With that route, you're basically looking at some variant of the Mass Effect system, which I think is the best version. The alternative, where dialogue is written on the fly, is obviously much harder but more interesting. I think a way to tackle this might be to start with the concept of knowledge. What does each character know? You might think in terms of topics or objects that are found in the game. Each topic or object has a number of categories (location, ownership, history, etc.). Now think in terms of a three-dimensional table that plots topic, category, and character. Each box contains a tick (the character knows that fact) or a cross (the character doesn't know it). For example, you might have Knife (topic), Location (category), and Janitor (character). If he knows where the knife is, that box will contain a tick.
Now you can think about how conversation could work. You might allow the player to choose a question type, which would correspond to the categories. For example, "Where is the...?". She could also choose an object to ask about, such as "the knife". Result: you ask the janitor where the knife is. If he knows where it is, he will tell you. If he doesn't, he won't.
Now that system is relatively simple. But it could be expanded upon to become more interesting. For example, it would be easy to add the ability to
tell NPCs things. If the janitor doesn't know where the knife is, you could tell him. The array containing everyone's knowledge would be updated, and from then on, he knows. NPCs could tell
each other things. Suppose you tell the janitor where the knife is, and then the supervisor comes in. The janitor now tells the supervisor where the knife is. It's easy to imagine interesting game situations arising from this sort of thing. It is usual in games to make conversation between NPCs entirely scripted, but with this system, you could make NPC-NPC conversation follow the same system as PC-NPC conversation, and that is more interesting.
Or even better: what if, instead of just a tick or a cross in the knowledge array, you have more detailed information. For example, under Knife -> Location -> Janitor, you might have "in the cupboard". This is interesting because now you have the ability to give characters wrong information! Perhaps the knife is actually in the shed. Ask the janitor where it is and he will give you misinformation. Now we have the possibility of correcting NPCs' information - or, even more interestingly, of lying to them. Lie to the janitor about the location of the knife and perhaps he will pass the misinformation on to the supervisor. What happens then?
You could add complexity by adding additional tags to each entry in the knowledge array. You could, for example, have each entry contain not only the information itself ("in the cupboard", in this case), but also how the character learned this information (who told him, or whether he saw it for himself), whether the character is inclined to be truthful about this information if asked about it, and so on. In our example, perhaps the janitor tells the supervisor that the knife is in the cupboard, when in fact it is in the shed. The supervisor goes to the cupboard to find it and is angry at the janitor. The janitor protests that the PC told him it was in the cupboard. The supervisor goes to have a word with the PC!
This kind of system is interesting not simply because of the complexity of beliefs and behaviour that it allows but because it gets us away from the "player asks NPC question - NPC responds" model of conversation which has become so cliched in games. Sometimes it seems like every NPC is just a sort of encyclopaedia on legs, ready to dish out endless information in response to the player's endless questions. What is really needed is a conversation system that will allow NPCs to take the initiative and behave in believable ways. I think the system I've just suggested might work as a basis for starting to put something like that together.