Avoid collecting flags, if you can help it, until the last chapter. This way, all of the roads are open, all sections of all cities are open, and you can keep better track of what flags you do and don't have.
Stick to the rooftops, if you can help it. It makes traveling faster and safer. This is much easier when you unlock throwing knives.
Take out archers as soon as you can. Guards in high places can spot you for those on the ground. When you are out of knives, a nice running kill with the hidden blade is a good substitute.
When on rooftops, practice your freerunning. It makes avoiding enemies much easier if you are being pursued, and makes informer/flag capture missions much easier if you are skilled at this.
If you are surrounded, the short blade is often a better choice than the long blade. It is weaker than the long blade, but slightly faster, and delivers more deathblow counterattacks. If you are a skilled at blocking, countering and the combo kill, it is a formidable weapon.
For assassination targets, aim for the stealth kill rather than taking them on head-to-head. They are tougher, faster, and more resourceful than guards in open combat, but just as susceptible to a knife in the neck.
For informer assassinations, stick to the roofs and use eagle vision. Hit the gold targets with knives. When there are more than two, it makes getting to them faster and less likely to expose you.