The word "Sudoku" actually comes from a Japanese phrase containing words beginning with "Su-" and "Doku-". The word "Sudoku" was simply invented, much like "Hi-Fi" comes from the phrase "High Fidelity".
Roughly translated, the phrase means "the numbers must be single". This of course is referring to the basic rules of the game.
The game itself, however, is not Japanese. It was invented by an American named Howard Garns, who originally called it "Number Place".
The game became popular in Japan in the 1980's, where it was renamed "Su Doku". The new name stuck.
In November 2004, The Times of London started publishing Sudoku on a daily basis, and from there its popularity exploded.