We have developed an efficient method to generate highly active Pd and PdO nanoparticles (NPs) dispersed on graphene and graphene oxide (GO) by an impregnation method combined with thermal treatments in $H_2$ and $O_2$ gas flows, respectively. The Pd NPs supported on graphene (Pd/G) and the PdO NPs supported on GO (PdO/GO) demonstrated excellent carbon-carbon cross-coupling reactions under a solvent-free, environmentally-friendly condition. The morphological and chemical structures of PdO/GO and Pd/G were fully characterized using X-ray diffraction (XRD), X-ray photoelectron spectroscopy (XPS), and transmission electron microscopy (TEM). We found that the remarkable reactivity of the Pd/G and PdO/GO catalysts toward the cross-coupling reaction is attributed to the high degree of dispersion of the Pd and PdO NPs while the oxidative states of Pd and the oxygen functionalities of graphene oxide are not critical for their catalytic performance.