While the "cult of the new" tends to mean that games aren't played many times before players move on to the next game, replayability is still a desirable feature of any game.
Most of the following amounts to "vary the experience", which of course is what provides replayabilty--varied experience:
• "Multiple paths to victory"
• Variable rather than set starting positions
• More than two players
• Asymmetric game
• Use of event cards
• Optional rules
• Different sets of rules
• Hidden information
• Special abilities
"Multiple paths to victory" will result in much-improved replayability. Drawback: makes it much harder to balance the game
Variable rather than set starting positions (players choose their starting positions). A few games offer both options. Risk offers a random setup and a setup that lets players choose locations. The drawback: this lengthens the game.
More than two players (each player provides variability of himself). The drawback: lengthens the game.
Asymmetric game (standard starting position is not the same for all players). The drawback: makes it much harder to balance the game (i.e., give each player an equal chance of winning).
Use of event cards (especially in symmetric games or games without other chance factors). The drawback: can be seen to increase the influence of chance. But event cards often adds enjoyable color to the game as well.
Scenarios (which amount to differences in positions or victory conditions (or both)). Used primarily in historical games. The drawback: more time-consuming to design.
Optional rules. Again this seems most common in historical games. These are alternative ways to play the game. At some point, many rule choices in a game design are largely arbitrary, that is, one choice leads to just as interesting a game as the other choice, but the designer must choose one. The other can become an optional rule.
The drawback: virtually none, if the optional was tried sufficiently in playtesting.
Different sets of rules (for example Basic, Standard, and Advanced). The drawback: longer rules, and perhaps a feeling from some contemporary players that there's something wrong with the game because there's not "one way to play".
Hidden information. The game can diverge along many different paths when some information is hidden. Event Cards are an example of the use of hidden information, and electronic games typically enjoy the benefit, as the computer tracks the information much more easily than non-computer methods can. The drawback: something/someone has to track the hidden information, and in some cases, cheating may be possible.
Special Abilities. Cosmic Encounter thrives on the variety of special abilities for each side. Role-playing games typically include a vast number of skills, feats, spells, and classes, not all of which can be included in any single game or series of games. The drawback: play balance can suffer; and there's a lot of information to be devised and incorporated into the game.
Finally, people have suggested that, in general, the more chaos in a game, the more replayability it is likely to have. Even Go, which has none of the overt variation I've listed above, is highly replayable because a single move can change circumstances fairly strongly.
Another point of view is that when the number of reasonable choices is maximized, replayability is enhanced. But too many choices can also lead to "analysis paralysis".