I personally do not find preserving fish to be worthwhile, as fish are plentiful and the nutritional yield vs effort on dried fish is pretty low compared to other food sources (smoked meat). That said, if i do catch more fish than I can use at one time, I will preserve the excess.
Choosing a location for settlement is as much personal preference as anything. My biggest requirements are as follows:
1) Close to water (1-2 map tiles, or closer). Rapids are better, lakes or rivers are fine. the Sea also works very well.
2) Close to a mountain, preferably only a short walk away. This makes a good lookout point, to see incoming threats or game animals.
3) Plentiful game - I like to scout around for an area that seems to have many large animals such as elk and reindeer. Sometimes reindeer herds will stay in one area for a long time, and you can gradually cull the herd to obtain large quantities of meat and fur.
Spruce mires or coniferous forests make the best areas for settlement, as there are plentiful trees for building and usually more wildlife. Marshes and mountains are too much of a pain, not enough trees and too hard to get around. However, caves can be a very effective way for a character with low building/timbercraft skills to quickly set up a permanent base, especially if there is a forest tile nearby for easy timber harvesting.
As far as order of construction goes, I follow something along the lines of PALU's protocol. The absolute first, and most critical element of any settlement is the cellar. I often build cellars all over the world, as food caches. When I worked in Alaska, one of the first things we would do when making a new camp is build a "tundra fridge", or a section of tundra cut down to permafrost. It really does preserve food remarkably well.
Anyway, cellar comes first, then a sauna/smoker for preserving food. Traditionally, ancient Scandinavians would build the sauna first and then sleep in there whilst constructing the main house. This is a very sensible system.
After constructing the sauna, the next steps just depend on your situation and your goals. If my character has poor building/timbercraft skills, is nomadic, or lacks specialized axes, i may just use the sauna permanently as my base (or one of my bases). For most characters with decent building skills, I will build a simple 4x4 cabin which seems to be sufficient for most needs. For skilled builders or more sedentary characters, I will build a large compound with several buildings and plenty of fenced-in space for livestock and farming. I don't have a formalized layout that I prefer, I just do every character differently depending on the priorities, and what the area has to offer.