Classical particle density distributions, approximated by floating Gaussians, are used to efficiently sample different structures in order to locate the global minimum on the multidimensional potential surface of van der Waals and water clusters. The Gaussian density annealing (GDA) approach of Ma and Straub [J. Chem. Phys 101, 533 (1994)] provides a set of equations of motion for Gaussian widths and centers. These equations are used to anneal the system from high temperature, with large Gaussian widths describing the particle density distribution, to low temperature. In order to ensure a quasiequilibrium throughout this process, certain constraints are imposed during the annealing. The results of structure optimization of van der Waals clusters using different variants of the GDA are compared. These applications demonstrate the advantage and efficiency of our method, a variation of the GDA algorithm, which anneals on consecutive levels of lower temperature. Extensions of the approach for atomic systems to include rigorous bond constraints in molecular clusters are also presented. Water cluster structures are investigated and compared with other theoretical calculations. Our findings suggest that the nature of the underlying free energy surface may diminish the efficacy of the GDA, and related methods, in locating global minima for clusters.