Planning in partially-observable dynamical systems is a challenging problem, and recent developments in point-based techniques such as Perseus significantly improve performance as compared to exact techniques. In this paper, we show how to apply these techniques to new models for non-Markovian dynamical systems called Predictive State Representations (PSRs) and Memory-PSRs (mPSRs). PSRs and mPSRs are models of non-Markovian decision processes that differ from latent-variable models (e.g. HMMs, POMDPs) by representing state using only observable quantities. Further, mPSRs explicitly represent certain structural properties of the dynamical system that are also relevant to planning. We show how planning techniques can be adapted to leverage this structure to improve performance both in terms of execution time as well as quality of the resulting policy.