Probably the most fertile ground for discovering new ways of telling a story within a computer mediated environment is through examining the many professional and amateur Web fictions. The thrill of such easy access to an audience and tools which make creating hypermedia simple and cheap has made this an area of extensive exploration and swift development.
Hypertext Hotel (1994) organised by Robert Coover and WaxWeb (1994) created by David Blair were two of the earliest Web stories available. Interestingly their Web presence was merely an extension of previously created MUDs. This left the Hypertext Hotel Web site a potential space with little in the way of characters or plot. WaxWeb began as a documentary film. Its MUD allowed people to elaborate upon sections of the documentary that had been translated to the Internet, and therefore the Web version did not seem like the hollow shell of a world waiting to be populated. Although, the documentary story did have the difficulty of being so interconnected as to be impenetrable due to the resulting stilted flow. Sensemedia's The Sprawl (1994) was the first example of a proper combined Web MUD where you could actually see the character interactions on the Web, as well as within the MUD.
Others soon broke away from the connection with MUDs to develop fully Web based stories. Cochran Communications took an innovative step in 1994 when they developed an interactive branching story based on Theodore Tugboat, a children's television show. This is a particularly well put together work which can be travelled through in many ways, and still end with a satisfying and complete story. Children's computer mediated stories tend to be of a higher quality than any other genre, and the techniques developed for this genre can be readily applied to adult storytelling as well. I suspect that people who create for children are more connected with the quality of play and the fluid nature of make-believe games. These become useful tools when turned to the creation of computer mediated stories. An Australian example of this would be Alex's Scribbles (1996).
Other Australian Web hyperfictions, but created for adults, are 24 Hours with Someone You Know (1996) written by published author Philippa Burne and the lyrical Henro (1997) by Edwina Breitzke.