Accidental spills and persisting hydrocarbon pollution caused by petroleum exploitation have deeply disrupted marine ecosystems, including those in the deep oceans and the Arctic Ocean. While physicochemical methods are available for emergency cleanup, microorganisms are ultimately responsible for mineralizing the hydrocarbons. The understanding of environmental effects on the composition and efficiency of hydrocarbon-degrading microbial communities has greatly improved current microorganism-based remediation strategies. This review summarizes recent findings on the physiology, metabolism, and ecology of marine obligate hydrocarbonoclastic microorganisms. Strategies for improved biotechnological solutions based on the use of hydrocarbon-degrading microbes are discussed for hydrocarbon remediation in marine water columns, sediments, beaches, and the Arctic.