City count is your primary goal. That means:

1.) finding settle-able spots, and settling them fast

2.) clearing monsters

3.) Being prepared for the +3 unrest per city penalty as you expand

Solutions:

1.) is solved by scouts, but just your sovereign exploring the map early on can find settle-able spots. Take even the crappy spots at first, you can cherry-pick geography later.

OR you can attack weak enemy players immediately and take their cities. Size 1 towns have pitiful militia defenses.

2.) On easy, one way to get rid of monsters quick is to spam out cheap, weak units early on. Go to unit design, edit the scout so that he only has the "weak" trait and a staff. Call them "peasants" or "peons" or something, then save it. This unit sucks, but costs almost no wage and usually trains in 1-2 turns. Train 5-6 of them, sending in another to reinforce your sovereign when they die.

You'll need strong well-designed units later, but making these cheap "peasants" early on takes the heat off your sovereign, and can artificially swell your power rating, improving early diplomacy.

3.) Bell towers and town halls are your friend, build them soon after settling a city.

Where are your difficulties? Are the monsters killing you or the AI?

If you have 5 cities by turn 100, you are probably going to win.

One more tip: play as altar or a custom "Men" faction, build henchmen.

Things I wish I knew when starting out.

When to just start a new game.  The random maps can sometimes screw you.  So scouting early on is very important just to determine whether your start position is viable.  If you don't see at least one really good expansion nearby -- a spot with two essence (or two decent spots - 3-4-1, 5-2-1) -- quit to the menu and start a new game.  Once you have the hang of the game though, the added challenge of resource-poor starts can be a lot of fun.

Use your essence slots.  Always make sure your cities have their all their essence slots used.  Spells like enchanted hammers, inspiration, or oppression can really juice your early game production.  Meditation (+1 mana per essence per turn) is a great spell for the early game as costs nothing and ensures a steady source of mana.  Set In Stone (+50% production, no research) can be an incredibly powerful spell for forts.

Protect your champions.  Yes, you should be splitting your champions into their own armies.  But don't let them or your sov fall in battle.  Missing turns of exploration/monster hunting in the beginning of the game is painful.  Provide support troops (you can custom design peons, as davrovna suggest -- or just use the pre-designed militia units) and try to position them so that they take the brunt of the attacks.  Buff your champions.  If you have the mana for it, buffing your champions is vital.  Don't be afraid to buy your champs food from the merchant to quickly heal your low level champs up to full strength.

Ignore monsters that are tougher than you.  Eventually, your armies will be able to take on the most dangerous monsters on the map.  But at the start and middle of the game there are a lot of baddies that will swat you like a fly.  Don't mess with the Dark Wizard.  Don't hang around Dragons or Skaths or Umberdroths.  Monsters usually wont bother you unless you bother them first, so steer clear and bide your time until you're ready to take them on.

Farm low level mobs around your cities.  Monster lairs that are outside of your ZoC will respawn.  After you defeat a bear/spider/mite hoard, leave the lair.  In 20-40 turns or so, a new mob will spawn and you can quickly swoop in a gobble up that XP.  Of course, if the AI is wandering around nearby, you'll need to take the lair to prevent the AI from stealing your loot.

Rushing can be a viable strategy.  If you get a couple lucky loot rolls and pick up a couple good weapons, you might be able to rush the AI's capital while his armies are out exploring.  Gather your champs and your toughest units and attack.  If you win the battle, you'll get a great city (probably a gold mine) and set the AI back quite a ways.  But be careful, because if you lose, you'll be pretty weak and the AI will be gunning for you.

Oh absolutely, I'll edit my post to make that clearer.

Couple more pieces of advice.

Play to your strengths, minimise your weaknesses.

Each faction has strengths and weaknesses, which you can learn to maximise or exploit.

E.g. Playing Gilden with Lord Markin you can make use of their cheaper weapons/armour and upgrades, combined with the Ironeer Blood (boosts Hit Points and Spell Resist) and Markin's Armorer profession (+25% Defence for the faction), to field some very tough units. However you might want to minimise Tactical Spell use as they'll cost 50% more.

You can also sometimes compensate for a faction weakness with Champion gear. e.g. Last time I played Yithril I used a Champion with a bow (bought from another factions shop, which you can do if in their territory and have decent relations) in my main army, as Yithril have no ranged weapons, but it was useful in some situations to pick off enemy casters/archers.

Know your enemy.

Before attacking an enemy group, check each unit's details. If you get attacked you can still check the enemy unit's details on the tactical map by clicking on their portrait on the left hand side. If you take the time to check, it will help you in the battle.

E.g. If an enemy has low or no cold resist (or even negative, such as the Quendar) then your Cold spells will do more damage. On the other hand, there's no point using a Lightning spell against an enemy that is immune to lightning, it just wastes mana.

Treat any unit with Maul (e.g. Bears) or Coal Stones (e.g. Wildling Shaman) as more powerful than it appears. I've lost quite a few units and even champions to those two abilities. Also if your army only has physical attack, avoid Banshees unless you can bring spells to bear or have items like rings, amulets or special weapons that add non-physical (cold, fire, lightning and/or poison) attack. That "Immune to physical damage" ability is a killer. 

Variety.

This is less about winning and more about having fun and replayability, but try out different things. It really depends on the player, but I find it can be a lot of fun not always choosing Mage for your Sovereign. Try an Assassin Soverign or a Defender (or Commander or Warrior.) You can also try Role Playing a bit, choosing the speciality or decision that your character would choose, even if it isn't the optimal one. Playing Pariden I chose Mage as Procipinee seems to be one, where as with Yithril I went for a Warrior Sovereign as that most fit Lord Vega to my mind.

Also be flexible. You might set out to conquer the world as Yithril, but you may find yourself in a position where that goal is less likely (e.g. You can hold your own, but aren't able to expand) in which case it may be worth pursuing an alternate victory condition.

Hope that helps.

All the Best.

A few more things:

(1) If you're not content with your starting position, you can use "CTRL+N" to quick-start a new game if (and only if) you never left the game and loaded a saved game after starting. So start a new game, play a few turns until you have a good impression of your surroundings and if things look too bad, start over.

(2) This also applies to "finding loot that sucks" in the first few camps you explore. In my first game, I had the incredible luck of finding two attack dog companions ("Anna") in the first 20 turns, which essentially gave me two free move-5 scouting units. Combined with playing as Tarth (no movement penalties and wandering monters tend to ignore you) this made for incredibly fast exploration. In the game I'm playing currently, I have lots of axes and spears (my sovereign is a mage) but nothing really useful except the telescope (+1 sight).

(3) Don't be afraid of low-grain spots if they offer other benefits. A 1-5-2 spot can make a great Fort. City size comes in time as you research the "faction food" improvements, but this can easily have double the production of any other location, especially if it's located near a forest. Also, there's an enchantment which will add one grain to a city.

And the primary rule can't be repeated often enough:

Expand fast. Build a new pioneer unit as soon as you can. As odd as that sounds, build them *especially* in low-grain settlements. Pioneer units cost population, and the low-grain settlements usually reach the population cap (you see this on the details window) fast in the early game. Basically, every turn your population isn't growing in a city is a waste.