Signals from radio pulsars show a wavelength-dependent delay due to dispersion in the interstellar plasma. At a typical observing wavelength, this delay can vary by tens of microseconds on 5-yr time-scales, far in excess of signals of interest to pulsar timing arrays, such as that induced by a gravitational wave background. Measurement of these delay variations is not only crucial for the detection of such signals, but also provides an unparalleled measurement of the turbulent interstellar plasma at astronomical unit (au) scales. In this paper we demonstrate that without consideration of wavelength-independent red noise, 'simple' algorithms to correct for interstellar dispersion can attenuate signals of interest to pulsar timing arrays. We present a robust method for this correction, which we validate through simulations, and apply it to observations from the Parkes Pulsar Timing Array. Correction for dispersion variations comes at a cost of increased band-limited white noise. We discuss scheduling to minimize this additional noise, and factors, such as scintillation, that can exacerbate the problem. Comparison with scintillation measurements confirms previous results that the spectral exponent of electron density variations in the interstellar medium often appears steeper than expected. We also find a discrete change in dispersion measure of PSR J1603-7202 of ̃2 × 10-3 cm-3 pc for about 250 d. We speculate that this has a similar origin to the 'extreme scattering events' seen in other sources. In addition, we find that four pulsars show a wavelength-dependent annual variation, indicating a persistent gradient of electron density on an au spatial scale, which has not been reported previously. © 2012 The Authors. Published by Oxford University Press on behalf of the Royal Astronomical Society.