It's a good game, more or less like the first, so if you liked that you're safe getting this one.
As Lingwe suggested, you should get Shadow Magic - it has more races, units and some interesting new gameplay mechanics, like the shadow plane, for example, an another level on the world map (like surface and dungeon) with a few twists.
The exploration, army management, combat and magic system are pretty much the same.
The town management system was changed, however. It kind of reminds me of the one in Master of Magic. There are no more 1,2,3,4-sized towns that can never be changed like in AoW1, so any town you own can be made as prosperous and productive as the next one. I can't remember if population was a factor in AoW1, but it is in the second - the population level in towns can grow, and once it reaches a certain point, your town will grow in size and get increased income and production values. There are 4 levels, I believe - encampment, village, town and city. Encampment is a town in its "infant" stages, right after you build it with a pioneer. You can build next to nothing in an encampment and will have to wait some time before it grows into a village.
And yes, now you will have to build different structures in your towns, like in MoM. These can be split into 4 groups - military, production, temples and magic. Military structures are needed to train soldiers and give you access to more powerful ones, production structures increase the town's production (reduce build time) and allow construction of siege weapons, temples generate mana and allow to train priests and magic buildings are all about, well... magic and spells.
The migrate, pillage and destroy options are still present.
What I didn't like is that they replaced the leader unit, whose stats and skills can be manually configured and improved through leveling up, with the wizard. The wizard is similar to the leader from the first AoW, except that he can't level up, his combat stats can't be configured/modified and his only purpose is to sit in a town with a built mage tower, to provide you with a "magic domain", a territory where you can cast spells. If the mage dies, he pops up in the nearest town with a mage tower, and if there is no such towns under your control, than it's game over.
Another thing they ruined is the town siege battles. I remember when you attack a town in AoW, it's size on the combat map was impressive, and it depended on the actual size of the town on the world map. Well, in AoW2 there is no difference what you attack - a huge city or a village, it will be of the exact same size on the combat map. Not to mention every town on the combat map is the size of a guard tower - a small square shaped territory surrounded by a wall.
And, as Selenti mentioned, the storyline sucks.
Apart from these, I don't have any complaints about the game, so if you liked AoW1 and want a good TBS experience - get this one.