Objective:
1. Find Shaera's father, Gramin.
Carries Over:
1. Elwin (max level 15)
Maps
Click on a map to see a larger version.
First Leg
Elwin starts out with the summon wolf spell, and that plus his weak combat skills should get you through the initial two battles. Then continue following the path, flagging troop buildings and only attacking what's in your way. The idea is to get to the first neutral town as quickly as possible and with as many troops as possible.
Once you take the town, feel free to go back and collect some of the things you missed before. In particular you should fight the earth elementals to get the wand of fire bolt. That'll help you way more than any other artifact on the map, and with elves in your army the earth elementals should be easy to defeat. You might also want to pick up the mage robe, but the medicine cart is guarded by 50+ bandits, and it probably isn't worthwhile to pick up anyway.
Note: As you gain levels, don't focus completely on your Nature skills. The second scenario will give you all sorts of ways to gain Nature skills, and so you should leave several advancement opportunities open.
Then explore east of your town a little and flag the windmill, treetop lodge, and gold mine. There is also a neutral Chaos town in the area, but you might want to avoid it until you can build up your army a little. Past the Chaos town to the east is a dead end that contains some creatures to kill and artifacts to pick up. Once you do what you want to do there and take the Chaos town, head north past Orange's domain. (It's protected by a keymaster gate, and you can't access it yet.)
If you go north at the intersection, you'll find one of Blue's towns. It might be difficult to take, depending on what spells you know and what you have in your army. But try to summon creatures to protect your troops from ranged attacks, and use your elves and wand of fire bolt to kill the enemy ranged attackers. Then, when the enemy melee attackers sit behind the walls doing nothing, summon in a large force of wolves (or better, if you have it) and let them charge the gate. Once the gate is down, you should be able to pick off the enemies with your wand and elves while the summoned creatures distract them.
Second Leg 
Once the Blue town is yours, you'll find a few useful buildings nearby, including another gold mine. Also, if you go back to the intersection and head east, you'll find an underground passage at (79,76) and a quest hut at (77,94). The passage is required for progressing through the scenario, so take on the Chaos group guarding it when you have a big enough army. (If you're having troubles with the battle, and if you have more money than you know what to do with, you can use an army of Might or Chaos troops to soften up the Chaos guardians before attacking them with your main army.) The quest hut will give you an arrow of stunning for a ring of strength (carried by a nearby neutral hero with some evil eyes), so complete the trade if you think it's useful.
When you go underground, you'll find yourself in the middle of a long tunnel. If you used the Window of the Magi near your first town, then you'll see that the southwestern end is where you want to go. There you'll find the orange keymaster tent, allowing you to enter Orange's lands, and also a two-way portal to the northeastern end of the tunnel, allowing you to scoop up some treasures without having to face the monks guarding them.
When you get back above ground, head for Orange's area. You'll find the blue keymaster gate near the entrance, but it leads to a treasure area guarded by cyclopes, and the cyclopes will probably damage your army too much to make the treasure (mainly a summoning amulet) worthwhile.
You'll also, of course, find one of Orange's towns in the area. But there are a few reasons not to attack it: you don't need to attack it, you'll probably reach level 15 without attacking it, it'll probably have numerous ranged troops guarding it, and it's a Chaos town. Also, once you pass the Orange town to the north, you'll find a Nature town, and it'll probably be lightly guarded. So take that town instead, and then hang around it for a couple days while you ferry in troops and build up the town to have a level 2 druid's hall. You can also take the opportunity to flag the nearby resource buildings.
Finishing Up
Then head east. Shortly you'll find Blue's second town. You might want to try attacking this town, depending upon how well it's defended. Blue's main hero will probably inside, and that hero will probably have artifacts and tactics, meaning that even without cyclopes the inhabitants might cause you problems. So save first and then try attacking it. If you can take the town without losing too many troops, then do so just for the experience.
Otherwise, continue heading east. You should encounter Orange's other town, but again it will probably be too difficult to attack. So instead head south to the coast where you'll likely find a stack of behemoths. This will be your last battle, so feel free to sacrifice all your troops if necessary to win. But between the behemoths and the treasure chests they're guarding, you should end up pretty close to level 15, if not actually making level 15. Then head north through the quest gate and meet up with Gramin and complete the scenario.