With interactive branched video, the storyline is typically determined by branch choices made by the user during playback. Despite putting users in control of their viewing experiences, prior work has not considered how to best help users that may want to quickly navigate, explore, or skip parts of the branched video. Such functionalities are important for both impatient users and those rewatching the video. To address this void, we present the design, implementation and evaluation of interface solutions that help users effectively navigate the video, and to identify and explore previously unviewed storylines. Our solutions work with large, general video structures and allow users to effectively forward/rewind the branched structures. Our user study demonstrates the added value of our novel designs, presents promising tradeoffs, provides insights into the pros/cons of different design alternatives, and highlights the features that best address specific tasks and design aspects.