Mix Your Fleet
When you play Battleship, mix up where your fleet is placed. If you put your ships in an arrangement that can be guessed (such as one ship in each corner, or along the same axis, or all of them touching) then once your opponent catches onto the pattern, your fleet is doomed. Also, if you place your ships in one arrangement during one game, make sure that you don't put them in that same arrangement for future games. Being predictable is what gets your battleships sunk.
Don't Guess
When you choose where to fire your shots to locate your opponent's ships, don't just pick random places to fire at. Think of Battleship like chess; you don't move a pawn just because it's there to be moved. Try and puzzle out exactly what your opponent is thinking and take your shots accordingly. Also, use some logic. If you've sunk all ships but the aircraft carrier, don't look for it in sections that are simply too small to conceal it from your guns. It will save you a lot of time.
Be Sure
Always double check when you're giving answers to your opponent's shots. If you say hit, and they record a hit, then make sure the shot actually did damage one of your ships and didn't get just close. If you or your opponent start retracting statements and making corrections then it starts to look fishy and accusations of cheating may begin to fly. If it helps, mark on your water segment (the part resting on the floor where your ships are) with white pegs when your opponent misses. That way you have to look at the spot he called out and peg it.