American Scientist has a great article on the mathematics of Sudoku. The author, Brian Hayes, first gives a brief history tracing the origins of Sudoku and its spread across the world. One interesting tidbit: many Japanese know the puzzle better by its original English name, "Puzzle Place", while most enthusiasts in the US and UK know it better by its Japanese name, "Sudoku".

Hayes also discusses the number of possible distinct solutions (3,546,146,300,288, or 4×10^12, once you've accounted for a number of symmetries), the minimum number of 'givens' required to solve a puzzle, and the relative strengths and weaknesses of solving methods a computer might use.