Visual surveillance in the maritime domain has been explored for more than a decade. Although it has produced a number of working systems and resulted in a mature technology, surveillance has been restricted to the port facilities or areas close to the coastline assuming a fixed-camera scenario. This dissertation presents several contributions in the domain of maritime surveillance. First, a novel algorithm for open-sea visual maritime surveillance is introduced. We explore a challenging situation with a camera mounted on a buoy or other floating platform. The developed algorithm detects, localizes, and tracks ships in the field of view of the camera. Specifically, our method is uniquely designed to handle a rapidly moving camera. Its performance is robust in the presence of a random relatively-large camera motion. In the context of ship detection, a new horizon detection scheme for a complex maritime domain is also developed. Second, the performance of the ship detection algorithm is evaluated on a dataset of 55,000 images. Accuracy of detection of up to 88% of ships is achieved. Lastly, we consider the topic of detection of the vanishing line of the ocean surface plane as a way to estimate the horizon in difficult situations. This allows extension of the ship-detection algorithm to beyond open-sea scenarios.