The recent emergence of Internet-of-Things (IoT) technologies in mission-critical applications in the maritime industry has led to the introduction of the Internet-of-Ships (IoS) paradigm. IoS is a novel application domain of IoT that refers to the network of smart interconnected maritime objects, which can be any physical device or infrastructure associated with a ship, a port, or the transportation itself, with the goal of significantly boosting the shipping industry toward improved safety, efficiency, and environmental sustainability. In this article, we provide a comprehensive survey of the IoS paradigm, its architecture, its key elements, and its main characteristics. Furthermore, we review the state of the art for its emerging applications, including safety enhancements, route planning and optimization, collaborative decision making, automatic fault detection and preemptive maintenance, cargo tracking, environmental monitoring, energy-efficient operations, and automatic berthing. Finally, the presented open challenges and future opportunities for research in the areas of satellite communications, security, privacy, maritime data collection, data management, and analytics, provide a road map toward optimized maritime operations and autonomous shipping.