We pay proportional taxes on the % of income that comes from other states. For example, if 80% of our revenue comes from Illinois and 20% from Michigan--we only pay taxes on the 20% from Michigan.
"Doing business" (as far as our accountant is concerned) is having billable clients in those states--generating revenue. We've had employees in 3 states (MI, IL and FL) and the only concern is making sure you are meeting that states payroll tax and withholding policies.
On a related note: Some states have different workers comp laws. We we're not required to carry workers comp in Illinois, but did need it in Michigan (and we also had to insure our Illinois employee, because she was now working for a company that was based in Michigan).
It's a confusing mess sometimes--seek help from accounts and lawyers and don't be afraid to call the state and just ask.
I've found that calling government offices can sometimes be extremely helpful.
Civil servants are often very smart, and sometimes very bored. Also, unless they are in a position where they regularly face the public, talking to "civilians" can scare them a little - they don't want to be accused of stuffing up. (As long as you are talking off the record, not getting written advice - they hate paper-trails. Written advice is to "double check" that it's all OK).
They can really go out of their way to give free advice.