There are several ways to go about it, and my strategy differs from the one used by Shrimp.
If you start in autumn you ought to be able to find berries with limited effort. Berries aren't particularly good for staving off starvation, as picking and eating berries constantly just slows down the rate at which you starve (although I've see the claim that you can actually hover on the starvation threshold indefinitely on berries alone).
However, berries are good bait for birds, i.e. in lever traps and snares. Note, though, that an autumn start means little time to prepare for winter (my characters start in "spring")...
Personally I tend to travel a for the first few hours to locate a decent spot for an early game camp (close to water, good terrain for hunting nearby), after which I set up lever traps around the camp, with the traps being placed in lines. I then expand this to similar trap line sites a few tiles away.
Once this has been set up, I check the traps once per day, processing the birds (and occasional hare) I might catch as I go. Note that you may want to skip skinning/tanning some of the time, as that's very time consuming (although it does train an important skill).
Once this baseline has been set up, I then try to roam around in search of "real" prey by zooming out, move one tile, zoom in, turn 180 degrees, zoom out, turn 180 degrees, move another tile....
This allows me to find tracks and an occasional bird that I can throw rocks at (they rarely hit, but sometimes you can down a bird and kill it).
When hunting elk/reindeer, open terrain is the best, so you can follow tracks and then see the animal at a large distance and move directly towards it, thus moving a shorter distance than the animal did. Once I scare it so it runs, I follow, try to track it, and when catching up I check its status. Once it shows signs of tiring, I then start to run towards it as soon as I catch up to get it to flee, at which time I immediately returns to walking speed. It's possible to gradually tire the animal so it builds up more and more fatigue for each encounter, until it gets completely out of breath, at which time you can walk up to it and bash it to death.
If you can get an animal to run back and forth along a bend in a river, you can tire it fairly quickly, and that works with animals such as hares as well.
Note that the above tactics are by no means guarantees of a kill: animals get away more often than not, although many attempts to get the same animal over days may eventually succeed.
When you manage to kill a large animals and it's too warm to dry the meat (one advantage with the "spring" start is that you can dry meat during the early phase, and thus build up a small backup stash of fairly non perishable food), I typically keep some of the meat raw (for later roasting) and roasts the rest. Once the hide has been processed, it's typically time to sleep, wake up, process the hide a second time, but then it's off to the nearest village to barter roasted meat for preserved food and/or useful items (keeping 20-30 cuts for near term consumption).
I don't fish much with my characters, but haven't used the new fishing system to any extent.
While it's somewhat annoying that you may have to bash an unconscious bird in the head a lot of times to kill it, note that each attack is a valuable skill training attempt, so I consistently use blunt attacks (even with spears) against all non dangerous targets. Blunt attacks before the animal is unconscious cause the least damage to the skin, and once it's knocked out attacks should be aimed at the head (and they never miss), which doesn't degrade the skin.
If you see a wolf: back away and leave. If you see a bear: back away and leave. A pack of wolves is extremely dangerous, while a bear is "just" very dangerous. I never attack either animal if I have a choice.
Another early character trick: you can opportunistically steal the kill from a predator either by scaring away e.g. an owl from a bird it killed, or getting a few cuts from a kill they've left behind. It's not glorious, but it's some valuable cuts of meat.