A storytelling game is an occasion where a number of participants gather to invent an interesting tale together. Usually, each person takes care of one or a few characters in the developing story. These characters are often reused in different stories, and players often bond quite closely with their alter ego. At least one participant takes the roles of a number of supporting characters, as wall as introducing non-character forces (for example, a flood). Since this person usually sets the ground and setting for the story, he or she is often referred to as "the storyteller".
In contrast to impromptu theater, storytelling gamers describe the actions of their characters rather than acting them out, except during dialogue. So called live action versions exist, though, which are very akin to theater.
Storytelling games can be seen as a sub-genre of role-playing games, where the game rules are deemphasised in favor of creating a believable story. So while in a conventional role-playing game the announcement that one's character is going to leap over that seven-meters-wide canyon will be greeted with the request to roll a number of dice, a storytelling gamer that wants to have a character perform a similar feat will have to convince the others why it is probable and "in-character".
But even storytelling games have a set of world rules (possibly including our own laws of physics, maybe augmented or even replaced by "magical" rules) so that not everything is possible. If every problem can be instantly solved, that does not make an interesting story.
It takes a certain kind of gamer to enact in good storytelling, one that is more interested in the path to a goal than reaching it. Many role-playing gamers are more comfortable in a system that gives them relatively less freedom, but where they do not need to police themselves.
Examples of commercial storytelling frameworks: