In more than two decades of research and practical experiments in interactive digital narrative (IDN), much insight about the relationship of narrative and digital media has been gained and many successful experiments have been undertaken, as a survey of the field illustrates. However, current approaches also limit the scope of experimentation and constrain theory in interactive narrative forms original to digital media. After reviewing the "interactivisation" of legacy theory (neo-Aristotelian poetics for interactive drama, poststructuralism for hyperfiction, 20th century narratology for interactive fiction and as a general theory for IDN), the thesis introduces a theoretical framework that changes the focus from the product-centered view of legacy media towards system and the process of instantiation. The terms protostory describing the overall space of potential narratives in an IDN system, narrative design for the concrete assemblage of elements and narrative vectors as substructures that enable authorial control are introduced to supersede legacy terms like story and plot. On the practical side, the thesis identifies limitations of existing approaches (e.g. legacy metaphors like the timeline, and authoring tools that support only particular traditions) To overcome these limitations a software toolset built on the principles of robustness, modularity, and extensibility is introduced and some early results are evaluated. Finally, the thesis proposes an inclusive, open-ended iterative process as a structure for future IDN research in which practical implementations and research co-exist in a tightly coupled mutual relationship that allows changes on one side to be integrated on the other.