The thermal behavior of NO on (flat) Pd(111) and (stepped) Pd(112) has been investigated by temperature programmed desorption (TPD), high resolution electron energy loss spectroscopy (HREELS), and Auger electron spectroscopy (AES) techniques. NO is shown to adsorb molecularly on both Pd(111) and Pd(112) in the temperature range 300-373 K. NO desorbs molecularly from Pd(111) near 500 K with evidence for slight NO dissociation. In contrast, on Pd(112), in addition to NO, relatively large amounts of N-2(7x) and N2O(15x) are observed to desorb near 500 K, compared to Pd(111). This result indicates that the influence of the step sites on Pd(112) is to catalyze the decomposition of NO upon heating. This is a surprising result in light of the fact that NO molecules preferentially bind to terrace sites, instead of step sites, on Pd(112). HREELS measurements indicate the presence of small amounts of surface-bound O (resulting from NO thermal decomposition) coadsorbed with NO on both Pd(111) and Pd(112) after NO adsorption at 373 K, followed by 490 K annealing. In addition, HREELS provides evidence for the existence of subsurface O formed only on Pd(112) during this procedure. The presence of steps on Pd(112) presumably offers an efficient pathway for O incorporation within the outermost Pd layers, as no spectroscopic evidence for subsurface O exists for Pd(111). Annealing both surfaces to 550 K induces the diffusion of both surface O and subsurface O into the Pd bulk.