You don't have to seek out a nature reserve or other recognized birding area to have an enjoyable time watching birds in Norway. Recently I spent a week visiting family in Valldal during the fall, and went looking without any idea what I might find. There was plenty to look at then, and some months later I returned in the late winter.
Valldal is a farming valley in Norddal, with steep mountains enclosing a mix of cultivated farm land, wooded areas, and a river that goes through the center of the valley. For the most part, the birds I found here were in the trees.
There was the ubiquitous Hooded Crow, which I seem to encounter wherever I go in Norway, as well as many Yellowhammers and White Wagtails. I also saw a pair of Eurasian Bullfinches, male and female, and a Greenfinch.
Valldal is a place where you can see a lot of pretty Tits (try to say that with a straight face -- it's not easy!). I've seen many Great Tits, Willow Tits, and Blue Tits in Valldal, often in or around fruit trees.
These birds all are common in Norway, but not one of them can be seen where I live in Illinois... rarity is in the eyes of the beholder.
Returning to Valldal by boat one afternoon from a fishing trip in the fjord, a number of eagles were circling high above, flying out from the craggy mountain peak across the fjord and seemingly following as we returned with our catch. They were extremely high up, and tiny to the naked eye. Having since enlarged a photograph of one, I'm fairly sure it was a White-tailed Eagle.
Down the road a short way from Valldal, in Tafjord, I saw a large colony of Grey Herons lurking about near the fish farm in the fjord. I've seen many Cormorants in the fjord as well.
Valldal is an area where the beauty of the surroundings contributes a lot to the experience of any outdoor activity, birding or other.
I don't think this is unusual in Norway -- if you're planning to be in any part of the country, it's worth going out to see what you can find in the way of birds.