A distributed video-on-demand system is one where a collection of video data is located at dispersed sites across a computer network. In a single-site environment, a local video server retrieves video data from its local storage device (or devices). However, in the setting of a distributed VoD system, when a customer requests a movie from his/her local server, the server may need to interact with other servers located across the network. In this paper, we present three types of presentation plans, that a local server must construct in order to satisfy the customer's request. Informally speaking, a presentation plan is a detailed (temporally synchronized) sequence of steps that the host server must perform at given points in time. This involves obtaining committments from other video servers, obtaining committments from the network service provider, as well as making committments of local resources, within the limitations of available bandwidth, available buffer, and customer/client data consumption rates. The three types of plans described in this paper all work at different "levels of abstraction" in this planning process. Furthermore, we introduce two measures of how good a plan is: minimizing wait time for the customer, and minimizing a quantity called access bandwidth (which informally speaking, specifies how much network/disk bandwidth is used). We develop algorithms to compute optimal (w.r.t. the above measures) plans for all three types, and show experimentally that in all three cases, one of the three types of plans (called a hybrid presentation plan) systematically outperforms the other two. In addition to these new concepts, our framework has the advantage that many results that had previously been verified experimentally in the literature can now be conclusively proved mathematically. (Also cross-referenced as UMIACS-TR-96-91)