Surface activity of heterogeneous catalysts can be enhanced if their sizes are reduced to nanometers. However, loose nanomaterials pose potential health and environmental risks. This issue has been addressed by attachment of palladium nanoparticles on multi-scale hierarchical carbon supports that have exceptionally high surface area per volume. The supports consist of porous carbon foam whose surface has been either chemically functionalized, or morphologically altered by grafting of carbon-nanotubes. It is seen that whereas chemical functionalization does provide some increase in nano-catalyst loading, morphological modification is significantly more powerful. It has the potential to create orders of magnitude increase in catalytic activity within the same overall volume. The synthesis techniques have been investigated in sufficient detail to provide significant control over the density and size of nanoparticles. Abundant distribution of nanoparticles is observed even within the deeper pores of the microcellular foam. The nanoparticles are seen to be metallic Pd having face centered cubic structure. Additionally, the nano-particles and nanotubes are durable, and remain attached to the base support after long periods of rapid rotation in water. These robust hybrid structures show promise in future applications such as sensors, water purification systems, fuel cell electrodes and hydrogen storage sponges.