One way was that I bought the book Solitaire Battleships, with a whopping 108 puzzles, ordered by category. I grabbed a pen and started doing these puzzles and timing myself during my daily commutes. After about a week, I had finished all puzzles (I commute about 2 hours every day). The total time spent was about eight hours, so I estimate two hours were spend in between puzzles while writing my times down. That sounds about right -- and that's an average of four and a half-minutes per puzzle! Not bad, considering I spent more than half an hour on one puzzle alone.
If you're just starting with Battleships problems, I suggest reading the very good introduction in the book Solitaire Battleships. It tells you about all logical techniques (that I know of) that can help you solve Battleships problems, with the dubious exception of the uniqueness assumption (it mentions it in passing, but doesn't delve into the intricacies of it and you could easily miss the mention).
Even with the uniqueness assumption (which doesn't come in use that often), I believe that there is no fast way to solve certain Battleships problems with only logical techniques. At least, not if you want to solve the tough problems in less than five minutes. So what techniques did I use? I can think of a few which I'll describe below.
The first is to get an instinctual feel for when you've reached a dead end. This just requires a lot of practice to build up your intuition. While solving, I often guessed a location for a ship and quickly felt "Hmm, I think I'll get stuck if I keep on going." I would then whip out the eraser and try another location. Occasionally my instincts were wrong and I ended up eliminating the correct answer, which explains some of the horrible times on some of these problems!
This means that to do well, you must also learn to distinguish between dead-ends that you're confident on and ones that you're not, so you know which path to go down if you get stuck having eliminated all possible paths. If you're confident that such-and-such a guess was wrong, don't revisit it; but if you're not so confident, by all means revisit it when you've exhausted all other options!
The second technique is to learn about "piece swapping." I'll write a whole new page about it, since this is pretty useful but will need some graphics. It's worth mentioning that it doesn't work very well with the awesome Battleships software Fathom It! though.
A few things are worth mentioning: