I'd say the place to start would be with the Taiwan Consulate General's office nearest you. The'll be able to tell you about visa requirements.
Also, there are schools that when they hire, offer to help you with this process, or seem even offer to take care of the paperwork for you.
That's at least a place to start. And there's a series for traveling called Culture Shock Taiwan amazon.com has it for $10.37 that might help out a bit too.