It's relatively easy (compared to crossword puzzles) to create a program which generates a limitless supply of sudoku puzzles of varying difficulty (the example in Xrenity's post is an extremely easy one). Most likely your local newspaper already has a daily sudoku puzzle in it and it's often done by commuters, so a handheld version is no surprise. There were already a few homebrew PSP versions of it before an official PSP version was announced, and I wouldn't be surprised if a DS version popped up. Plenty of them for PDA's too.
A bit disappointing that the recently released Ultimate Puzzle Games for the GBA doesn't have any Sudoku puzzles, though it makes up for that with plenty of crosswords, cryptics, and wordseekers.