Fishing:
I've been keeping a spread sheet, and I've had luck using berries, leaves, roots, and mushrooms, in addition to the more obvious baits of meat and fish.
meat and fish make the best baits, then leaves and roots are about half as good as those, berries are a big worse than leaves and roots but still all right, and mushrooms are a lot better than nothing, but not as good as berries.
Even with nothing you will sometimes get a roach or a perch and then you should use that as a bait for another fishing round
Trapping: I like to put all kinds of traps in the same general area, with a fence, and bait them with berries, roots, and eventually meat too (spoiled raw meat works fine, cooked or dried or smoked meat doesnt work so well). Each day I reset the traps to train up my skill and eventually it pays off.
Active hunting: this gets less annoying once you have a dog to tire the prey out, before that you want to be good with a bow and arrows or very patient or stick to pine mires.
If it's the time of the year when the ice is thin, wander around along the edge of lakes looking for animals that got overconfident and fell through the ice