For large animals, I really recommend you first finding some before actually putting down traps. Finding an Elk/Reindeer, put a trap or minor trap fence on the location, maybe bait with a turnip, and voila, you'll get it. And it's quite likely that more animals will eventually appear on the same general area, instead of hoping you lucked out on spot you picked actually being somewhere they tend to go. Bears similar thing, just use meat instead of turnips.
Foxes: Same as before, but easier because you can use paw-traps. Raw meat is best bait, raw fish works too. I've heard stories of preserved/cooked meat working, but I haven't had as much luck with those.
Birds: Loop snares and/or lever traps all around wherever you're staying. Doubly so around your cellar and your field. They now can fly over the traps, mind you, but enough should be landing nearby, trying to steal your food or peck your crops. So trap your "reality bubble", and give it time. You'll probably be catching a whole damn bunch whenever you stay there for multiple days.
Hares: Never had any luck trapping those. Maybe loop snares around berry bushes I guess?
Most small animals: Small deadfall traps are useful, specially if baited with the appropriate thing, but you'll probably want first to find the animal or at least tracks. Meat on small deadfall traps can be really powerful given the value of the furs of some of tho
A note: Be careful with heavy deadfall traps. As I understand traps still have some chance of spawning appropriate animals near it. And one of the animals for heavy deadfall traps are wolves. Which come in packs and are an absolute nightmare to fight. Very valuable, yes, but incredibly dangerous too. I'd rather fight a bear naked with a single knife than a pack of wolves, even with proper equipment. So, do not put them in the immediate vicinity of your house. And remember that, once you get a house, you can shoot arrows and throw javelins through windows, so if you do get a wolf infestation, shoot from inside.
For actually trapping wolves, yeah, heavy deadfall traps, with at least some distance from your base, and, very importantly, let all non-trapped wolves leave before you try to grab the carcasses (because you might also want to let the trapped ones die naturally instead of accelerating it for safety sake).
Finally: Remember, keep the spirits happy. Do a general sacrifice daily (they don't seem to mind if your sacrifice is not valuable, caloric, or even poisonous, just so long it's not spoiled, so feel free to sacrifice berries, mushrooms, and whatever else you can find), and use any other appropriate spells you might know.
As an addendum: It's not as easy as it used to be anymore, but you might also want to consider trapping the most valuable of preys: Foreign traders. Upon finding a group and more or less figuring out their heading, some staked (important, because you want them to bleed to death without your direct involvement) pits on where they will eventually be can net you incredibly valuable goods. Do keep in mind that if they see you making a given trap pit they won't fall for that one. And they are pretty good at noticing trap fences, even if you use just a wall of trap pits instead of any actual fence, so make use of natural chokepoints, and careful to not make it too contiguous.