Long story short, a bunch of people terraformed a planet and then were immediately technologically and societally forced back to the Stone Age thanks to interference/extermination/general-not-goodness on the part of some other people who could nonetheless not be half-assed to finish the job. They've been building their way back up for a few millennia; assume that technology-wise, they're identical to Earth in all ways except for those related to fossil fuels.
However, this planet was terraformed from what was essentially a barren rock, meaning it never had millions of years for the remains of dead life-forms to decay into fossil fuels - the people in question arrived, terraformed (took about 500 years), got obliterated as a society (took about 1), and have been evolving back into a modern society since (took about 15,000). It takes fossil fuels significantly more than 15,501 years to form.
The principal origin of fossil fuels is the anaerobic decomposition of buried dead organisms, containing organic molecules created in ancient photosynthesis. The transitions from these source materials to high-carbon fossil fuels typically requires a geological process of millions of years, sometimes more than 650 million years.
This means that, once technology hits a level where steam-powered ships would have otherwise come into the scene, things instead go differently, since steam-powered ships run off of coal or oil, both of which are fossil fuels, and do not exist on this planet. Moreover, naval air power would be significantly different, since there's no jet fuel. Later on, your WW1-through-WW2-level battleships will be different, since there's no oil for them to burn.
For the purposes of this question, this planet is functionally identical to Earth other than the fact that it does not have any fossil fuels.
The question: How would modern naval warfare be altered by a complete lack of fossil fuels?