The main contribution of this paper is the development of Planning by Rewriting, a novel domain-independent paradigm for efficient high-quality planning. First, we define a language of declarative plan-rewriting rules and present the algorithms for domain-independent plan rewriting. The rewriting rules provide a natural and convenient mechanism to specify complex plan transformations. Our techniques for plan rewriting generalize traditional graph rewriting. Graph rewriting rules need to specify in the rule consequent the complete embedding of the replacement subplan. We introduce the novel class of partially-specified plan-rewriting rules that relax that restriction. By taking advantage of the semantics of planning, this embedding can be automatically computed. A single partially-specified rule can concisely represent a great number of fully-specified rules. These rules are also easier to write and understand than their fully-specified counterparts. Second, we adapt local search techniques, such as gradient descent, to efficiently explore the space of plan rewritings and optimize plan quality. Finally, we demonstrate empirically the usefulness of the PbR approach in several planning domains.