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:
See also letter game storytelling