Here are some notes, in response to requests and repeated misinformation in this forum and elsewhere. Please note that the author is not a legal expert, just a pedant who gets frustrated at people who make basic mistakes due to not knowing what they're talking about. If you want better advice, go to the legal forums, this is just an introduction to the topic.
Work permit vs visa: A visa allows you to be in Taiwan, but does not give you permission to work. A work permit allows you to work, but does not give you permission to be in Taiwan. You need both documents, from different government departments, in order to be working and living legally in Taiwan.
This can be confusing because you need a visa to be in Taiwan, but you need a reason (eg a work permit) to obtain a visa. So there are usually several steps to follow. First, you arrive with a visitor visa (or visa-exempt entry), then you apply for a work permit, and this allows you to obtain a new visa as an employed person. An ARC is simply proof that you have a visa, it doesn't permit anything.
Getting a visa: A visa basically says that someone representing the Taiwan government has considered your circumstances and concluded that you should be allowed to enter Taiwan for a limited period of time. The visa may permit you to enter Taiwan more than once, and will specify how long you can stay each time. The visa usually has a limited validity period, after which you need to get a new one. Note, a visa does not actually guarantee that you will be permitted to enter Taiwan, but I've never heard of anyone having problems entering Taiwan with a valid visa.
Visas are generally issued overseas at Taiwan's representative offices. You may be required to provide them with photographs, bank statements, and official proof of the reason why you are visiting Taiwan. Good reasons include study or some kind of business trip. If you tell them you plan to look for work, they will probably not approve your visa application. If you already have a job lined up, you will need to provide a lot of documentation from Taiwan to verify the legality of that. (see below) It's generally easier to do this paperwork once you arrive in Taiwan.
No matter what the reason for your visit, visas issued overseas are generally only good for one or two months anyway. They are known as visitor visas, and are issued for the purpose of tourism, study, etc. (I don't think they are officially called tourist visa or student visa.) You will need to get a new visa once in Taiwan, if you plan to stay longer. This is generally known as a resident visa, signifying that you are resident in Taiwan, and allows you to come and go as you please.
Visa-exempt entry: If you're from the developed world, you are probably able to enter Taiwan without a visa. If you arrive in Taiwan without a visa, but you have a return ticket to leave the country again, you will be allowed to stay for a period that varies according to your nationality. US citizens are generally allowed to stay for 30 days, UK citizens for 90 days. So you don't actually need a visa to come to Taiwan initially.
Landing Visa: I've never met anyone that had this document, but if you come from a country that is not approved for visa-exempt entry, and don't already have a visa, then you will be required to obtain one when you arrive in Taiwan.
If you're planning on teaching in Taiwan, then you should be from a country that also qualifies you for visa-exempt entry. You should therefore delete the phrase "landing visa" from your operational lexicon. You will never need or see this document.
Why is this important? When you arrive at the airport in Taiwan, it is really nice if everything makes sense. It's great when you move forward with obtaining future paperwork if you are using the same (correct) terminology as the people who are telling you what you need to do. Try obtaining a landing visa from someone who is adamant that you should be visa-exempt and are in the wrong line. Asking for advice on this forum, but using the wrong terminology, is not likely to result in useful answers either.
The airlines and you: If you are denied entry to Taiwan, then the airline has a legal obligation to fly you back where you came from. To avoid this problem, airline staff will usually check your documents when you check in for your flight. If you don't have a return ticket or visa then they will probably refuse to fly you to Taiwan. If you don't have a return ticket, you need to get a visa before leaving for Taiwan.
Converting visa-exempt entry to a visa after you are in Taiwan: Officially, the last time I checked, it is not possible to obtain a first visa while in Taiwan. You need to enter with some kind of visa, and then change to a resident visa after you have the necessary documentation in Taiwan. If you enter without a visa, visa-exempt, then you should need to take short trip to Hong Kong (or anywhere else with a Taiwan rep office) with all your documents, to obtain a visa. Then you can complete the process of applying for residency and ARC. In practise, as at the date of writing this, it is often possible to obtain a visa while in Taiwan, despite having entered without one.
Work Permits: For ANY work in Taiwan, even unpaid volunteering, you need to have official permission. The first thing your employer should do is to apply for a work permit. This is issued by the Labor Department, and is generally obtained for you by your employer. They will need to provide copies of their business registration and license, together with your contract, qualifications and passport. Work Permits generally take several weeks to process, and you cannot work legally until this has been done. It doesn't matter if the paperwork is in process, you should have a copy of the permit in your hand before you do any work.
NOTE: If you have a job lined up before you arrive in Taiwan, it is possible to send copies of your documents to your employer and have them obtain the work permit in advance of your arrival. If they send you a copy of this (plus business registration, a copy of your contract, etc.) then you can use these to apply for a visa in your own country. But it will probably still be a visitor visa. You will still need to obtain a resident visa after you arrive. The only difference is that you would then be able to work at your job on the day you arrived in Taiwan.
The law does allow you to have more than one work permit, from more than one employer. A work permit permits you to work at the job specified, at the address specified, and nowhere else. You are not free to work for anyone else, or at any other location than the one specified on your work permit. If your school has two locations, they need two work permits. You cannot do private tutoring, babysitting, or help out at an animal shelter without written permission from the Labor Department.
Getting a resident visa: If you are legally employed, you are permitted to remain in Taiwan for the period specified on your contract. So you need to get a visa reflecting this fact. You have to go to the immigration department with about four million different pieces of paper and apply for a resident visa. Assume you will have to make three trips, one to fill in an application form and be told what else they want you to bring, the second to actually present all the documents, and the third to pick up your processed documents.
Assuming everything is OK, you should be legally resident in another week or two.
NOTE: You can legally work at your approved job during this time, as you have obtained permission to do so. Immigration is different from Labor!
Resident visas and ARCs: In the old days, resident visas were stuck into your passport, and you would then go to the police to obtain a certificate confirming that you were a) a foreigner (an alien) and b) legally resident. Alien Resident Certificate, ARC, simple.
These days, ARCs are issued by the immigration department and no visa is placed in your passport. Instead, there is a note on the back of your ARC stating that you are now allowed to come and go freely in/out of Taiwan. So an ARC appears to function like a visa.
In fact, the visa still exists within the computer system. When you leave or enter Taiwan, nobody will look at your ARC. They will check your passport and their computer will tell them about your visa status. The ARC is not a visa, it is proof of a visa to be used in your daily life so you don't have to carry your passport.
Some common misconceptions:
you can get a landing visa on arrival. Look, stop using that phrase, OK? Visa-exempt, means no visa, which is important because technically you need to go overseas and get a visa before applying for residency.
an ARC permits you to work. No, your work permit(s) tells you about your work status. Your ARC merely proves that you're allowed to be here. You can have an ARC without having any work rights.
your employer can cancel your ARC. No, your employer can terminate your job and must then notify the Labor Department. They then cancel your work permit, and notify the Immigration people that you no longer have a reason to be in Taiwan. They then cancel your visa, which means your ARC becomes invalid. You could maintain your residency (and get a new visa) by finding another job, getting married, etc.
this is all very complicated. No. Get a job, get permission to work in that job, get permission to be in Taiwan, pick up your ARC. It's simple.
government officials will try to prevent you working or staying. No, they are people who are paid to process paperwork to facilitate the economic life of the country. If you are polite and work with their system, they are usually very likeable and helpful people. If you are rude, try to bend the rules, etc., then you are making their life difficult and you will probably regret it.
I hope this helps. It's incomplete and I'm sure many others will add to it, but it's a start.