We have studied the nucleation and growth of Au nanocrystallites with dimensions of tens of nanometers on strontium titanate surfaces using an atomic force microscope. Strontium titanate ablated from a pressed pellet target by a KrF laser was deposited on both planar and offcut strontium titanate substrates. In a separate step, submonolayer quantities of gold were deposited, also by pulsed laser deposition, on the strontium titanate. The surfaces were then scanned by an atomic-force microscope to determine the effects of surface defects (such as steps and kinks on offcut surfaces), substrate temperature, and gold ablation yield on the nucleation, growth and size distribution of the nanocrystallites. The competition between diffusion and nucleation on planar vs stepped surfaces was particularly apparent in the AFM images. These results suggest several ways in which lateral decoration of the strontium titanate by the gold nanocrystallites can be achieved, an important step toward designer nonlinear photonic materials.