A puzzle game like Bejeweled or Tetris has randomly generated "levels", usually with a slow progression in difficulty. That alone can make a game interesting. Trying to get as far as possible, getting a "lucky streak" or scoring the most points.
One thing that's really important is that the gameplay feels right. Controls should be simple and intuitive, graphics and sound should support and enrich the gameplay. Clearing a level or scoring multiple points with one move should look and sound great, so that the player gets some sort of audiovisual reward.
It's a bit different with puzzle games that have pre-defined levels like physics-puzzles or games like "Slice it" or "Trainyard". The main goal there is to beat the game, eg. complete all levels. Additional replay-value can be added by adding better scores for fast or "flawless" solving of the puzzle.
Another important factor is progression. Either by trying to beat your own scores or scores from other players in a leaderboard. Once you mastered a game and you have the feeling that you can't get better, you'll most likely also lose interest in it.
The most addictive puzzle-game I've played recently is probably Puzzle Quest. It combines a Bejeweled-type of game with a fantasy story and RPG elements. Not only the puzzle-solving is addictive, you also want to progress in the story and "level-up" your character... addictiveness overload ;)