Heterogeneous unmanned systems consisting of unmanned aerial vehicles (UAVs) and unmanned surface vehicles (USVs) have great application potential in marine environments. At present, the fully autonomous recovery of UAVs is a key problem that restricts any significant application of a heterogeneous unmanned system. This paper presents a novel fully autonomous recovery system, covering the entire process of recovery of small fixed-wing UAVs on mobile platforms at sea. We describe methods or solutions for the key problems encountered by the current system, including active modeling of the UAV-USV heterogeneous platform motion model, accurate estimation of the highly dynamic relative motion of the heterogeneous platform, dynamic analysis of the arresting cable system, and compliance control of the manipulator recovery system. Based on these methods, a physical simulation platform for the fully autonomous recovery system, including an actively adjustable arresting cable, manipulator compliance recovery system, and other subsystems, is developed and verified through experiments. The experiments show that the system proposed in this study can achieve full autonomous recovery of a small ship-based fixed-wing UAV with a high success rate in a short period. This system is the foundation for practical applications of UAV-USV heterogeneous unmanned systems in the marine environment.