Many critics like to trace the beginnings of hypertext and hyperfiction to works such as the Talmud (completed circa 500), Tristram Shandy (1760-1767), and Hopscotch (1966). Pieces of textual information can be related to each other in a variety of ways as was done in these works. These relationships can be made apparent through topical discussion, chronology, theme, character, etc. and they may be most conveniently presented by a computer in a non-sequential manner. Hypertext is a system of inter-related documents presented on a computer. When this system is extended to other media such as music or film then it is known as hypermedia. Please note that a more recent term, interactive multimedia, is in fact synonymous with hypermedia. It was in 1960 that Ted Nelson first thought of a system of hypertext and he coined the term for a paper he delivered at the ACM 20th national conference in 1965. The Talmud, Tristram Shandy and Hopscotch are indeed what might be considered paper based examples of proto-hypertext, but none of these were in fact inspirations toward the creation of computer-mediated storytelling.
The two greatest influences in the development of digital storytelling would have to be the television show, Star Trek by Gene Roddenberry, which began in 1966 and the Lord of the Rings trilogy by J.R.R. Tolkein which was published during the period of 1954 to 1955.
The first widely played computer game was in fact called Star Trek which was released in 1967. People would actually learn programming in order to play and help develop this game on college campuses across the United States. Star Trek the game was not originally screen based at all, but done on print out paper. The purpose of the game was to explore the galaxy and rid it of Klingons. This was strictly a game within a story context, but without any real narrative content. Other games based on this one, or Star Trek the show, started taking on story at a much later time.
The next milestone in computer game history and what I would consider the best historical starting point for computer mediated storytelling, was the creation of Colossal Caves, a.k.a Original Adventure, in 1977 by Patricia and Willie Crowther, and Don Woods. It began as an interactive text description map of the very real Mammoth caves in the US by the Crowthers. When Don Woods had a chance to wander through this virtual space he thought it might be fun to throw in a dragon, a few dwarves and some treasure, and turn the program into a game with a Lord of the Rings feel to it. This sort of text adventure is known as interactive fiction or IF.
Both Star Trek and Lord of the Rings as stories have some distinctive features that are significant to the development of computer mediated storytelling. First, they both involve a unique but expansive geography. Space and movement through space become more significant aspects of the storytelling task when creating for the computer. A story will move along in all senses.
Next, Star Trek and Lord of the Rings are both episodic in nature. Some episodes build on one another, many provide insights into the characters and the world they live in. Though you may need to go through all episodes before the ending of the story makes any sense, nevertheless, it is possible to mix the episodes up and still come up with a coherent story. Computer mediated storytelling works best when the story is not slavishly attached to rigid plot movement. The overall experience may require some direction, but readers are in a position of feeling like active participants in the story as they have a chance to wander in on events under their own volition.
Finally, Star Trek and Lord of the Rings provide complex worlds with complex but easily graspable sets of characters and character interactions. People who enter into these worlds tend to understand the particular genre whether it is science fiction, fantasy or mystery, how it works and what is likely to happen in stories set there. Yet, plenty of scope is available for all sorts of stories to take place within the single story world. This conveniently confines what needs to be developed by a creator for the world to be interesting and feel complete.