The diffusion of small palladium clusters on MgO(100) is theoretically investigated. It is found that small clusters can diffuse even faster than isolated adatoms by a variety of mechanisms (some of which are novel), such as dimer rotation, trimer walking, tetramer rolling, and sliding. The consequences of the diffusion of small clusters on the growth of Pd aggregates on MgO(100) are investigated, and it is shown that fast mobility of clusters larger than a single atom is essential to bring the theoretical results into agreement with the outcome of molecular beam epitaxy experiments.