It is best to fish with a fishing rod because your encumbrances don't count against you.
If you fish with a spear, club, rock, or stone, you must drop everything you are carrying first and not be fatigued, injured, or starved, or you will have little chance of catching anything.
Nets not only generate a little extra food for any character, they are an excellent way to train Fishing to higher levels without wasting too much time. By accumulating 15+ nets, you have a reasonable chance to increase your Fishing skill each time you deploy them.
Nets are best set in calm water according to Sami. You cannot set them by swimming in 3.19. You need to make a raft and paddle. Sometimes there will be shallow water next to very deep water: you can see this by looking for light blue next to very dark blue. If you swim to that shallow place, you can set the net into deep water without a raft, but these places are rare, outside of rapids tiles. Sami said that you will get less fish if you put your nets in rapids tiles.
Fishing skill increases fairly quickly. If you start out with 0 skill and do nothing but fishing, you can increase your skill to a tolerable level before you starve to death if you have a fishing rod. Fishing rods are very cheap and you can buy one for about 5 cords made from your starting clothes, or your starting food. Most villages have them in the sauna.
Fishing is a good way to get into the game while you are just learning or while you are waiting for your traps to fill with elk or before you know how to do active hunting. Fishing isn't very exciting, however, so as you get better at the game you may find you spend less time fishing.
Active fishing is fishing using either a club, spear or fishing rod (in order of least effective to most effective). To do so, choose your fishing implement and pick a direction in which to fish. Fishing lasts for a long time, up to 3 in-game hours. Active Fishing does seem to actively use your Fishing skill, and ritual Fisherman's request for a catch. Use the ritual right before doing the fishing. Try to trade for a good or masterwork fishing rod in the village because club or staff or spear/trident is not that helpful.
Passive fishing is fishing using nets, which you must trade for, and can only be placed in deep water. After the net is placed (usually by boat or by swimming) you should check back on it in order to gather your catch. Checking is done through the fishing skill, and neglecting a net will mean its fish will rot. Use the fishing skill to set a net, and also to check it. After setting the net, wait for a minimum of one day and maximum of 2 days, then check it. Hopefully you will have caught something. It's best to arrange so that you check on every even or odd-numbered day so you don't forget. Multiple nets are a very good way of obtaining food and increase your fishing skill; however, if you forget to check it, the fish inside the net will rot, and you will have nothing to eat. Nets are only sold in certain villages' shops, therefore it takes time to find and gather them. You will start with two Nets if you take the "I want to be a fisherman" backstory, which can provide you with enough food to survive, meaning any extra you gather can go into storage in preparation for winter, or as an emergency supply if nothing is caught in a long period of time, or injury prevents you from gathering sufficient supplies.