1) create sales tax rules for different states :
Process :- Go to Sales -> Taxes -> Manage Tax Zones & Rates . Add your taxation for different states here.
2) Manage Tax Rules :
Process :- Go to Sales -> Taxes -> Manage Tax rules. If you haven't created rule, create and check all your tax rules for that. Keep the product Tax class as "Taxable goods".
3) Apply Tax Rules :
Process :- System -> Configuration -> Tax. (Under Sales Tab). After this, change your "Tax Class for Shipping" from None to "Taxable goods".
Your rules will be applied accordingly for different states.