At the very beginning my character makes a bunch of the smallest lever traps, as those can be made without anything you can't get through scavenging. I also have my character go from world tile to world tile, zoom in, look for game, zoom out, and throw rocks at bird that are sufficiently close. It has worked surprisingly well (i.e. mostly kept out of starvation).
Endurance hunting can be greatly improved by being lucky and some player skill to drive the prey to the bank of a river or lake and get them to run back and forth until they run themselves into the ground. It can be quite hard early on, though, as the tracking skill is generally rather poor. A key to endurance hunting is to keep the prey running and don't allow it to catch its breath. Looking at it you can see it being slightly fatigued, which means it will move a little slower. If you can press it you can get it to fatigued, which slows it down further. However, an elk or reindeer deciding to walk in a straight line will recover its breath while outpacing all but the fastest walkers. I used to never run, but have changed that to run towards prey starting to tire to get them to run again. As soon as they run I switch back to walking.
I give up if the prey has made so many tracks in an area that I can't follow them.
A javelin thrown at a reasonably short distance can hurt a prey sufficiently to slow it down, allowing you to whittle its breath down.
Also consider whether it's worth trying to hunt prey in spruce infested forests, as the visibility is horrible and the trees hide many of the few tracks your poor tracking skill can locate.
I don't get a dog until my character is "rich" enough to afford it and can provide enough meat to keep it fed (spoiled raw meat works well, so don't discard that).
I've rarely managed to sneak up on animals, although I rarely try... I've had a few cases of sneaking up on sleeping Njerps, killing them in their sleep, though.
I generally don't fish, as my experience is that it's a method of slowly starving to death, although net fishing works (not reliably, but it takes a sufficiently short time that you have time to get food using other methods). Nets are expensive, and so aren't options early on. Fishing rods are cheap, though. Also note that my characters tend to have lousy fishing skills.
When you've killed a bird, you may want to consider whether to spend the time and effort on preserving its skill, as it uses up a lot of time. Also, you can't perform the last step of leather making (whacking on it) if your character is unable to stand (e.g. due to an injury from the start scenario or trying to resist a starting scenario robbery).
Preserving the skin of 5 birds take a full day, and if it's hazel grouse the meat won't feed you fully. However, you tend to want leather and hide early on, so it's a balancing act.
I suspect the distance at which you can see animals is dependent on their size and your character's eye sight. Thus, elks, reindeer, and bears can occasionally be seen at quite a distance, while badgers, and gluttons usually are seen at a closer distance, and hares and birds are usually seen only on neighboring tiles.