The puzzle is generated using the solver to solve an empty Sudoku board. It implements a backtracking algorithm in which it randomly selects numbers to try in each cell. It starts with the first cell and picks a random number. If the number works in the cell, it recursively chooses the next cell and starts again. If all the numbers for a cell have been tried and none work, a number chosen for a previous cell cannot be part of the solution so we have to back up to the last cell and choose another number. If all the numbers for that cell have also been tried, we back up again. This continues until a value is chosen for all 81 cells. (The actual implementation is pretty much what is described here though it does use some optimizations and tricks so it isn’t too painfully slow. If you’re interested check out the source which is heavily commented.)
Once the board is filled in, values are removed until no more values can be removed without creating a puzzle with more than one solution. Actually, Medium and Hard are guaranteed to have only a single solution. Easy uses a naive algorithm similar to that used at the dhtmlgoodies.com link above which may have more than one solution. Don’t worry though, if you find a valid solution the game will finish.
Have fun. Send any comments, bugs, contributions to firstname.lastname@example.org