Adding Au to Pd nanoparticles (NPs) can impart high catalytic activity with respect to hydrogenation of a wide range of substances. These materials are often synthesized by reducing metallic precursors; hence, sonochemical and solvothermal processes are commonly used to anchor these bimetals onto thin supports, including graphene. Although similar NPs have been studied reasonably well, a clear understanding of structural characteristics relative to their synthesis parameters is lacking, due to limitations in characterization techniques, which may prevent optimization of this very promising catalyst. In this report, a strategic approach has been used to identify this structural and material synthesis correlation, starting with controlled sample preparation and followed by detailed characterization. This includes advanced scanning transmission electron microscopy and electron energy loss spectroscopy; the latter using a state-of-the-art instrumentation to map the distribution of Pd and Au, and to identify chemical state of the Pd NPs, which has not been previously reported. Results show that catalytic bimetal NP clusters were made of small zero-valent Pd NPs aggregating to form a shell around an Au core. Not only can the described characterization approach be applied to similar material systems, but the results can guide the optimization of the synthesis procedures.