I am running a Viking themed 3.5 adventure and the party is traveling to confront a barbarian king on the way though they have just been fighting wild animals and it feels like these encounters don't mean anything. I had a ranger hunting them with his wolverine companion but that was the only encounter that had any story. Any advice on adding story to my encounters?
Use the journey to deepen your players' knowledge and understanding of this barbarian king. Let the encounters illustrate his (and his underlings') personality and decisions. Maybe show him to have multiple sides, to be a person of grays instead of black and white, if you haven't done so yet.
An example: Have an encounter centered on refugees fleeing this king. Say, their cart (or ship or whatever) got into trouble, and they can't proceed, and the king's men (a small capture party) are catching up with them. Give your party the chance to help the refugees escape and/or fight the hunting party... but give it a twist (one, at least): Show that the refugees are, in fact, slavers: they have a few chained youngsters hidden (or out in plain sight?), who apparently haven't been treated well. These youngsters are from the king's people. Twist, once again: Even though the refugees are slavers, the youngsters are rapers and thieves who did hurt the refugees' families - that's why the slavers think enslaving them is proper punishment. In the eyes of the king's men, however, the refugees are just outlaws, though... but so are the youngsters, who would have to face even harsher punishment at the king's hands than slavery. Reveal this all relatively quickly, and have the king's men arrive (by an unexpected shortcut) in the middle of the debate. Try to turn it into a standoff, if possible, with talk first and combat later (or not at all.) Show what this king and his laws are like through the words of the opposing NPC parties.
Another example: Have your party come across a pillaged, burnt out village, with a few looters still there, picking what they can, killing the wounded etc. Reveal that this village belongs to the barbarian king, and that the cruel looters work for the same power (god, jarl, thane etc) as the PCs. The village was relatively unprotected because its fighting men went off to conduct a burial, from which they won't be back for at least a day. (Have the party learn this from someone: either a villager or a pillager.) Reveal that the looters - even though they're on the same side as the PCs - were about to plant evidence incriminating the PCs, at the behest of some internal rival (a nice way to introduce a mysterious one if you haven't done so yet. ;)) Make a villager or two a reliable witness of this - and then have the looters make a secret attempt on their lives. Then have the scouts of the villagers' returning warriors turn up and witness how the PCs handle the situation. Then show how the barbarians react to what they've seen. Maybe they'll like, in their grief, the PCs' actions, and try and put in a word for them with the king. Or not. It's up to what you wish the king and his rule to be and seem like.
So... something like this. Use the encounters you come up with to foreshadow the confrontation with the king. Once again, have NPCs and situations reveal what he's like, illustrate - through NPCs' actions, words, and opinions (of him and of his rule) - what the PCs can expect.
I think the best way to add story is to roll random encounters differently. Make your own table(s) and make the encounters make sense. Instead of
1d4 Wolves, have an entry of
1d4 Wolves (under control of evil local chieftain) tasked with destroying caravans or
1d4 Wolves forced out of forest due to fires set by BBEG. Make each encounter have a story, and let your players pick up on it (DM: "These wolves have whipmarks on their backs, and one has a bandage on its leg." P1: "They must be trained wolves!" P2: "I wonder who sent them?").
One way to do this is to have a few prepared encounters in a table, in more depth than you usually would have, and then use each encounter as you roll it, replacing it with another detailed encounter at the end of a session. Alternatively, you could change the encounter generation methods you are using to include a 'Motive' table describing why the monsters/people are there, and/or a 'Controller' table (that is region- or campaign-specific) describing who the guy calling the shots for them is. If the PCs then find out who the Controller is, a side-quest opportunity opens up.
An idea that is used in another RPG (Stars Without Number, a Futuristic/Post-Apocalyptic game) is to have factions. These are a good way of controlling and simulating large organisations, and also allow for easy story generation. Essentially, the part relevant to your question is that you can make encounters tell a story by making it about a faction (such as a large village, bandit clan or raider-captain in your setting) and its goals. When the
2d6 Bandits are attacking the PCs to get cash to pay off a bigger clan, it's more than just "Ho-hum, yet another bandit attack". Take inspiration from movies. There are generally few movies where the characters get regularly attacked by random fauna and people. In Lord of the Rings, for example, the good guys have a few enemies they regularly fight, under the control of a handful of bad guys. (There's and excellent webcomic about LotR called DM of the Rings.)
Your party could easily be aggravating local druids and rangers for the land they are in, which can put them in some pretty hot water with their own people. This can add depth if they are meant to be a good-aligned party, especially if they are in fact just hunting critters for the fun of it (XP) that can raise some alignment issues already.
Lastly, "There's Always a Bigger Fish" could come into play. If the same animals keep getting poached, then the natural balance of the land is disturbed. Those animals might have somehow been keeping something in check.
Without more information I don't think I can give you a better answer.
Speaking as a DM... I don't think those encounters mean anything either. Wild animal fights very easily fall into what was known in LARPing as "random damage." That is, fights that exist solely to fill out the quota of expected combat and don't serve any story related purpose whatsoever. Personally I don't use many "random" encounters, most of mine aren't actually random from my perspective at all and they're part of some storyline or another that's going on in the area. Maybe how I pick which one they encounter today might be randomized, but I very rarely ever use just a list of random encounters. (Of course, the players don't know that.)
There's a bunch of ways to come up with story, but the first thing you have to do is a mindset change. Instead of trying to add story to your encounters, you instead should want to add more story to your campaign. There is a world beyond what the party is doing, and occasionally the party will stumble onto something else that's happening while they're trying to do their main quest.
That secondary story will then add encounters, and dictate what the encounters should be. That might sound like the same thing, but it's not. If I were doing it I wouldn't be taking wild animals and saying "what story can I make to explain this?"
I'd start from something like what CatLord suggested above (the local Druids are aggravated over X), which is causing them to rile up the local wildlife. So that means a couple of animal encounters, and then maybe the Druids themselves show up and get mad at the party for killing the animals. At that point the party can choose to deal with the Druids, or maybe try to talk to them and instead help deal with whatever is aggravating them.
As to how to come up with those storylines, on top of the suggestions you've already been given, I like to talk to friends about the campaign. I have a couple of friends that aren't playing but like hearing about what's going on, and I bounce ideas of them and take ideas from them to incorporate. I've had a couple of side plots in the city my game takes place in appear because of them (one of which turned into a full session mini-adventure).
You can also look at your setting, and think about "if there's other Vikings and Barbarian tribes in the area, what would they be doing that doesn't already involve the party? Are there other groups or individuals acting in the area? What are their agendas?"
I'm not sure how helpful this is, but couldn't find a better way to articulate it. :)
I do it all the time. Just pick a free adventure from here which fits the group, change names, location etc' to fit the adventure better and you got yourself some cool, well designed encounters which can move the plot forward.