This paper is the first in a series of reports describing Nuclear Magnetic Resonance (NMR) and numerical modelling studies of the representation of the structure of porous media and associated transport phenomena. In this paper the interpretation of Pulsed Gradient Spin Echo (PGSE) NMR data are considered. In extending earlier studies in which the porous medium is assumed to be macroscopically homogeneous, we have considered the effect of spatial variations in both the diffusivity and relaxation properties within the porous medium, occurring over lengthscales of order > 100 mu m. Expressions for the log-attenuation plot and the diffusivity are derived. The theory gives excellent agreement with experimental PGSE data obtained for a variety of porous catalyst support pellets, and both the effective diffusivity of the materials and an indication of the degree of heterogeneity of diffusion are obtained. Sample tortuosities are found to be in the range 1.3-4.3. The results suggest that macroscopically heterogeneous materials have a greater tortuosity than more homogeneous materials.