In order to stop terrorism, it must no longer be acceptable to have countries give money, support, real estate for bases, legitimacy, etc. to their claims and actions. There is where the military battle must be fought, with countries that will support the actions of terrorists. We must work diplomatically as well to get those governments to freeze the funding, and to educate their citizenry about the horrors these people relish visiting upon the innocent.
The first step would be to clearly define the intent of the US against just such actions. Attacking Iraq was just such a step, but as I said before without the declaration of war it has become a "quagmire" to those who voted to send us there. Some give them a pass, without regard to their position when this conflict began. Simply, voting to declare war is a simple choice, either you vote for the war or against it you cannot hedge yourself into a safe spot in the future by defining your vote differently at different times.
Another battle to be fought is in Public Relations, in this we have made some errors. Instead of having Arabs dance in the streets when buildings fall after terror attacks in the US, our goal should be to have them embarrassed that actions were taken in their name that caused the deaths of innocents. This is the actual battle that we have not yet begun to really fight. The first step again would be successfully installing a powerful government in Iraq.