A game that involves strategy and tactics as the most important element. Often very much related to logic-based games.
Strategy games are often war-themed in one form or other, but some are just abstract. Go, for example, is more of "territory control" than "war", while Chess is obviously war-themed and gives you a little medieval army for hunting and killing the opponent's monarch.
Strategy games can be played on variety of methods; Some can be played with just paper and pen (or other writing surface), others require board and playing pieces, and some others just require computers for the enjoyment.
* Examples of board games: Famed classics chess and go
* Example of a more recent game, a favorite of mine: BattleTech
...
In computer games, there's often a difference between turn-based strategy games, where players can think of their moves as long as they have to (thus being similar to most "analog" strategy games), and real-time strategy games (RTS), where players have to control their forces as things unfold. Often, turn-based folks mock real-time folks, because often RTS games require just quick mouse clicks to win and no tactics sense, but personally, I think both are entertaining in their own ways.
* Examples of turn-based computer strategy games: Civilization, Sid Meier's Alpha Centauri, Steel Panthers
* Examples of real-time strategies: Warcraft II, Command & Conquer, Starcraft | 
