Control and tunability of the catalytic oxidation of CO by gold clusters deposited on MgO surfaces grown on molybdenum, Mo(100), to various thicknesses are explored through temperature-programmed reaction measurements on mass-selected 20-atom gold clusters and via first-principles density functional theory calculations. Au-20 was chosen because in the gas phase it is characterized as an extraordinarily stable tetrahedral-pyramidal structure. Dependencies of the catalytic activities and microscopic reaction mechanisms on the thickness and stoichiometry of the MgO films and on the dimensionalities and structures of the adsorbed gold clusters are demonstrated and elucidated. Langmuir-Hinshelwood mechanisms and reaction barriers corresponding to observed low- and high-temperature CO oxidation reactions are calculated and analyzed. These reactions involve adsorbed O-2 molecules that are activated to a superoxo- or peroxo-like state through partial occupation of the antibonding orbitals. In some cases, we find activated, dissociative adsorption of O-2 molecules, adsorbing at the cluster peripheral interface with the MgO surface. The reactant CO molecules either adsorb on the MgO surface in the cluster proximity or bind directly to the gold cluster. Along with the oxidation reactions on stoichiometric ultrathin MgO films, we also study reactions catalyzed by Au-20 nanoclusters adsorbed on relatively thick defect-poor MgO films supported on Mo and on defect-rich thick MgO surfaces containing oxygen vacancy defects.