We consider the process of changing reference frames in the case where the reference frames are quantum systems. We find that, as part of this process, decoherence is necessarily induced on any quantum system described relative to these frames. We explore this process with examples involving reference frames for phase and orientation. Quantifying the effect of changing quantum reference frames provides a theoretical description for this process in quantum experiments, and serves as a first step in developing a relativity principle for theories in which all objects including reference frames are necessarily quantum.