We present an analysis of the variations seen in the dispersion measures (DMs) of 20 millisecond pulsars observed as part of the Parkes Pulsar Timing Array project. We carry out a statistically rigorous structure function analysis for each pulsar and show that the variations seen for most pulsars are consistent with those expected for an interstellar medium characterised by a Kolmogorov turbulence spectrum. The structure functions for PSRs J1045-4509 and J1909-3744 provide the first clear evidence for a large inner scale, possibly due to ion-neutral damping. We also show the effect of the solar wind on the DMs and show that the simple models presently implemented into pulsar timing packages cannot reliably correct for this effect. For the f...