How to Win at battleships
There are two repeating phases in the game: Hunt and Kill.
In the Hunt phase you are trying to find ships. Since all ships occupy at least two contiguous squares, you only need to fire at every other square. If it was a checkerboard, you'd only fire on the red squares and not black, for example. Once you score a hit, go to the kill phase.
Kill phase obviously results in trying to figure out which way the ship points and where the ends are. In this case you fire immediately adjacent to the hit location. The rest you can figure out.
You can save some time by knowing which ships are still out there. If you have found the destroyer, you don't need to sample every other square, but rather every third, as the smallest ship will span at least three adjacent squares.
I'd start randomly firing off shots, but don't hunt in adjacent squares. Then you can fill in holes later after sinking a few ships and knowing which ones are still out there.
TL,DR; Every other square to find ships, then sink them.