Platinum nanourchins supported on microfibrilated cellulose films (MFC) were fabricated and evaluated as hydrogen peroxide catalysts for small-scale, autonomous underwater vehicle (AUV) propulsion systems. The catalytic substrate was synthesized through the reduction of chloroplatinic acid to create a thick film of Pt coral-like microstructures coated with Pt urchin-like nanowires that are arrayed in three dimensions on a two-dimensional MFC film. This organic/inorganic nanohybrid displays high catalytic ability (reduced activation energy of 50-63% over conventional materials and 13-19% for similar Pt nanoparticle-based structures) during hydrogen peroxide (H2O2) decomposition as well as sufficient propulsive thrust (>0.5 N) from reagent grade H2O2 (30% w/w) fuel within a small underwater reaction vessel. The results demonstrate that these layered nanohybrid sheets are robust and catalytically effective for green, H2O2-based micro-AUV propulsion where the storage and handling of highly explosive, toxic fuels are prohibitive due to size-requirements, cost limitations, and close person-to-machine contact.