At least two newspapers runs SuDoku puzzles:
The first one is 'Dagens Næringsliv' which is easily recognised by its pink colour. The puzzle is on the last page and range from easy to hard, with a rumour that they're preparing for 'Hellish', whatever they mean by that.
The second newspaper I seem to have lost the name for, but it's one sold in Oslo and surrounding area. (The puzzle is printed within the first 10 or so pages)
The third Newspaper is 'Aftenposten', and their puzzle isn't a real SuDoku, but with similar rules.
Theirs is made up of 2x3 blocks, and each block is 3x2 squares big. Only the numbers 1 to 6 is used and the numbers must be unique in the box and the horisontal and vertical lines.
There's a book 'Lær og Løs Sudoku' for sale in Norway. The first printing disappeared before I could buy one, though, but a new batch is expected soon. A new book in the series is also planned and will be published 'soon'.
While the 'lær'(Learn) part of it isn't of any interest for non-Norwegian speaking enthusiasts, it also contains a lot of puzzles.
Anyway, if you're stuck at an airport or hotel in Norway and need a brainteaser, this should help a bit.