Two players, about half an hour. (... to set up the board and another half hour to play :) - Kazuhiko)
Both players set up their counters on opposite sides of the board - so that their opponent cannot tell which piece is which.
The middle of the board has several areas which pieces may not move on to.
Players then take it in turns to move. Most pieces can only move one square in each of the four available direcitons. The exceptions are the scout (which can move as far as it likes but has a very low ranking) and the bomb (which cannot move)
Piece have rankings, and beat all pieces of lower rank and are beaten by all pieces of higher rank. When two pieces are on the same square, the losing piece is removed from the board.
The exceptions to this ranking are:
The spy. Can beat the marshall (and is the one of only two pieces that can do so) but is otherwise beaten by all other pieces.
The bomb. Beats EVERYTHING except for an engineer.
Play continues until one side captures the others flag, thus winning.
Fox Mulder and his sister Samantha were in the middle of a game of Stratego when the latter was abducted in the nineties conspiracy/sci-fi/horror series The X Files. It might have been aliens what did it; I don't know, it got crap after season two and I stopped watching.
There's a nice version of Stratego called Lord of the Rings - the Confrontation. One side controls the nine members of the fellowship, the other nine nastys. The goodies try to get Frodo to Moria, and the baddies try to kill him before he gets there. All the characters have special abilities, so Merry immediately kills the Witch King, the Witch King can attack sideways, etc.