I used to use the diagonals-separated-by-three method described by erislover, until I took a few art classes. There’s a general principle in 2-d art (painting, photography, etc.) that the main focus of your piece should not be centered. Rather, it should be at one of the four points one-third away from the edges, as this is more aesthetically pleasing. It seems that humans placing battleships have a tendancy to position their fleet aesthetically, too, so something resembling a tic-tac-toe grid (starting with the intersection points) seems to find most of the enemy fleet disproportionately quickly. I usually do try to keep my points consistent with an eventual diagonal or checkerboard strategy, though.
Conversely, most people who try to play randomly will also subconsciously form a pattern similar to the above, so keep your own ships away from those tic-tac-toe points.
Also, once you start hitting ships, your pattern (whatever it is) is going to break down eventually. At that point, you start looking for “how many possibilities can I eliminate with each shot”. At the extreme case, suppose that the board is entirely filled, save for one row of nine squares, and that the only ship left is the big one (5 spots, generally the carrier). There are five possible places the carrier could be in that. If you shoot at one of the ends, then you’ll only hit one of those nine, but if you shoot in the middle, you’re guaranteed a hit. Intersections of open lines are also good targets.
And you should try to sink the big ships first, because you might get the small ones by chance, but if you try for the small ones first, it’ll take forever.