This paper reviews design-based estimators for two-stage and three-stage sampling designs to estimate the mean of finite populations. This theory is then extended to spatial populations with continuous, infinite populations of sampling units at the latter stages. We then assume that the spatial pattern is the result of a spatial stochastic process, so the sampling variance of the estimators can be predicted from the variogram. A realistic cost function is then developed, based on several factors including laboratory analysis, time of fieldwork, and numbers of samples. Simulated annealing is used to find designs with minimum sampling variance for a fixed budget. The theory is illustrated with a real-world problem dealing with the volume of contaminated bed sediments in a network of watercourses. Primary sampling units are watercourses, secondary units are transects perpendicular to the axis of the watercourse, and tertiary units are points. Optimal designs had one point per transect, from one to three transects per watercourse, and the number of watercourses varied depending on the budget. However, if laboratory costs are reduced by grouping all samples within a watercourse into one composite sample, it appeared to be efficient to sample more transects within a watercourse.