Build a dock in one of your coastal cities. Then a dry dock will become available; built it, and a shipyard will become available. Now you can build a navy! As a bonus, each of these buildings gives ocean tiles +2 food, so they're worth building on their own.