I live and paddle on the north west coast of Norway, and would be more than happy to help if I can. As Nick says, you'll have to go north of Bergen if you want to see the typical Norwegian fjords. Sogn og Fjordane (with Sognefjorden, etc) and Møre og Romsdal (with the Geiranger Fjord, Runde, etc) are great areas to paddle and worth looking into.
I just paddled in Sunnfjord (in Sogn and Fjordane) and had a great time. To see some pics from this area, go to
http://www.njord.as, or
http://www.cse.ogi.edu/~walpole/Askvoll.html.
This summer I paddled from Geiranger to Runde with a few friends. That was also a great trip, and we got to see both the dramatic fjords and experience the open sea. But the area further south, between Stavanger and Bergen, is also great.
And you can easily move along the coast with Hurtigruten to find the perfect starting point. It's not too expensive, and you can bring your kayaks.
But how much time do you have? What kind of paddling do you want to do? And what kind of experiences are you seeking?
Just drop me a mail with specific questions and I'll do my best to help.
dag
dag@[remove]kayak.no