This paper concerns the creation of an efficient, continuous, non-parametric representation of surfaces implicit in 3D laser data as typically recorded by mobile robots. Our approach explicitly leverages the probabilistic nature of Gaussian Process regression to provide for a principled, adaptive subsampling which automatically prunes redundant data. The algorithm places no restriction on the complexity of the underlying surfaces and enables predictions at arbitrary locations and densities. We present results using real and synthetic data and show that our approach attains decimation factors in excess of two orders of magnitude without significant degradation in fidelity of the workspace reconstructions.