[Nick_K]

Don't forget to build lots of temples. I've seen more than a few posts in Dom3 and Dom2 where new players have lost the game because their dominion became too weak.
Against the AI, I first conquer a few provinces - usually all the ones connected to my capital - and then expand at a slower pace while building up a province defence of 10 in every province or 20 in ones which border an enemy and putting a temple in every single province. It's worth cutting your troop production down a bit to build the temples.

Also, choose your enemies carefully. Underwater nations are a bit tricky to defeat when playing as land ones so you might want to avoid fighting them at first.