A method and apparatus for providing an interactive menu structure within an interactive information distribution system. The menu structure is embodied in a combination of software, which provides a so-called navigator and a set top terminal that provides certain functionality for the navigator and a video session manager which provides support functionality for the set top terminal. The menu structure has each menu (e.g., menu instructions, graphics and video) contained in downloadable applets which are sent upon request from the service provider equipment to the set top terminal for display. As such, the navigator functions are actually distributed between the service provider equipment and the subscriber's equipment. Such distribution provides an enjoyable, real-time interactive session that allows the user to rapidly navigate through a plethora of menus to find particular information, which they desire to view.