When you create a shipping method, if you set a zone restriction in it, it will only be available in that zone. Before your users enter their address, the "main tax zone" will be used as the current zone of the user. Once the user enters/selects his address, the country/state of the address will be used instead. Having states or not for a country doesn't change that and so far, it worked for everyone as long as the shipping methods were correctly configured.
No tax will be set for your shipping methods if you don't select a tax category in them. You don't have to create a special tax category for them. That will also avoid any mistake you might have made while configuring your tax rules since the tax won't be calculated for shipping methods if they don't have a tax category.