You need not destroy everything, but you need your buildings in place of the local ones (unless your enemy is of the same culture). Temples should in fact be destroyed last as they often add rather substantial bonusses (+10% happiness and +10% law is not good to lose if you run around with 85% happiness). Shrines should of course be destroyed when you like it to, but never forget that most buildings can be upgraded into your own type of building, even temples (though that requires that you read the temple guide to determine which temples are compatible).