Starting Out -- Your First Move
In most maps you start with a castle with a sawmill and ore mine close by. Before you do anything, check to see if they are guarded. You can do this by pushing the enter button on your Pocket PC and pointing at the mill/mine. You can do this on all structures and enemies – it will give a general indication of the number of troops they have.
If they are guarded, then upgrade your town to the next level of troops and buy all the troops that are available. If they aren't guarded, skip this step (don't visit your town at all) and proceed directly to the resource sites to claim them.
Buildings
You need to buy a Mage guild 1, Marketplace, and City Hall. Those are your first priority. Just roam around picking up scattered resources and securing your one or two mills/mines while you build these structures.
You may have to skip a turn or two of building. For instance, you may have completed all the prerequisites for your City Hall, but lack the 5,000 gold to build it. Don't be temped to build anything else during this time. Just be patient and save up for the City Hall. turrets won't help you anyway.
Managing the Enemy
Save often and play around – you'll have to work on timing a bit. You don't want to leave your town unattended if there’s an enemy hero waiting around the corner to steal it from you. You don't want to go charging up to a mine only to find a very powerful enemy hero standing right next to it ... who will kill you on the next turn. It is better to have one really strong hero to withstand attacks from the computer.
Magic
Slow and Haste can be very useful spells. The former allows you to stop fast opponents from rushing your ranged troops; the latter allows you to better rush your opponents’ ranged troops. Lightning is one of the strongest offensive spells.
Skills
There a number of skills you can learn, but you can only learn a total of 8. Since your hero will start with 2-3 skills, that means you can only learn 5-6 new ones. Depending on personal preference, you may find certain skills more useful than others.
Saving prior to visiting Witches’ Huts can be a wise move, in case the witch teaches your Hero a skill you don’t value.