First, since you don't have experience in hand sharpening with a whetstone, I would suggest you watch some on-line videos on how it is done. Jon Broida at Japanese Knife Imports and Mark Richmond at Chef Knives to Go both have extensive series of videos on how to sharpen, using waterstones.
Second, read this post: http://forums.egullet.org/topic/26036-knife-maintenance-and-sharpening/
The minimum size will be 2 inches by 6 inches (50mm x 150mm). That's really a minimum. You are probably going to want both wider and longer. 8 inches (200mm) long by 3 inches (75mm) wide will be much easier for you to work with.
You are going to probably want at least 3 stones -
A coarse stone, in the 400 to 600 grit range, for reprofiling the edge or thinning the blade or doing repairs. This would be the stone you probably won't want to use too much - it's only for the times you need to remove lots of metal. And keep in mind one really important thing about this stone: You can always remove metal when sharpening - but you can never add metal!
The second stone should be in the 800 to 1200 grit range. This will be your primary workhorse stone, for restoring sharpness.
The third stone should be in the 3000 to 5000 grit range. This will be your polishing stone. It is also useful for touch-ups.
An alternative is the Edge Pro Apex sharpening system. This system uses a stand on which the knife blade rests, and specialized stones are moved over the knife edge. They create a consistently even edge when sharpening your knives, and require considerably less of a learning curve than freehand sharpening with waterstones. They are sold directly by the inventor, Ben Dale of Hood River, Oregon (http://www.edgeproinc.com/). You might want to also read a fairly recent post I made here: http://www.cheftalk.com/t/79668/a-few-questions-re-the-edge-pro-essential-set#post_459501 (I'm referencing it here, since I'm trying to get this to you as soon as possible, and most of the information would also relate to this thread).
Chef Knives to Go ( http://www.chefknivestogo.com/edgepro.html ) sells customized kits which have different stones from the original Edge Pro kits. I have the "Essential" kit, which uses Shapton Glass stones specifically set up for the Edge Pro systems. Check with Mark Richmond about whether and how he can ship to you in Norway.
The Edge Pro site lists several authorized dealers in the European Union area (I am guessing that Norway is part of the EU) and you might instead decide to order from one of those retailers. I am also thinking that you might want to go the "do-it-yourself" stone route, so I concentrated on retailers selling the Edge Pro Apex One kit. The least expensive I quickly found was Yankee Online ( http://www.yankeeonline.nl/products/detail.asp?pid=723 ), which offered the Edge Pro Apex One kit for 159.99 euros.
Hope that helps