The capability of autonomous operation of ship-based Unmanned Aerial Vehicles (UAVs) in extreme sea conditions would greatly extend the usefulness of these aircraft for both military and civilian maritime purposes. Maritime operations are often associated with Vertical Take-Off and Landing (VTOL) procedures, even though the advantages of conventional fixed-wing aircraft over VTOL aircraft in terms of flight speed, range and endurance are well known. In this work, current methods of shipboard recovery are analysed and the problems associated with recovery in adverse weather conditions are identified. Based on this analysis, a novel recovery method is proposed. This method, named Cable Hook Recovery, is intended to recover small to medium-size fixed-wing UAVs on frigate-size vessels. It is expected to have greater operational capabilities than the Recovery Net technique, which is currently the most widely employed method of recovery for similar class of UAVs, potentially providing safe recovery even in very rough sea and allowing the choice of approach directions. The recovery method is supported by the development of a UAV controller that realises the most demanding stage of recovery, the final approach. The controller provides both flight control and guidance strategy that allow fully autonomous recovery of a fixed-wing UAV. The development process involves extensive use of specially tailored Evolutionary Algorithms and represents the major contribution of this work. The Evolutionary Design algorithm developed in this work combines the power of Evolutionary Strategies and Genetic Programming, enabling automatic evolution of both the structure and parameters of the controller. The controller is evolved using a fully coupled nonlinear six-degree-of-freedom UAV model, making linearisation and trimming of the model unnecessary. The developed algorithm is applied to both flight control and guidance problems with several variations, from optimisation of a routine PID controller to automatic control laws synthesis where no a priori data available. It is demonstrated that Evolutionary Design is capable of not only optimising, but also solving automatically the real-world problems, producing human-competitive solutions. The designed UAV controller has been tested comprehensively for both performance and robustness in a nonlinear simulation environment and has been found to allow the aircraft to be recovered in the presence of both large external disturbances and uncertainty in the simulation models.