I am a South African, who go married in the beginning of last year (2004) to a Taiwanese lady.
Due to very confusing posts and being quite confused as to what to do next, this is the process I went through.
Firstly, getting married
I got married here in Taiwan. I was married by a Notary in Hsindian (新店).
At the "Notary public office of the Taipei District Court" located at No. 248, Chung-Hsing Rd., Section 1, Xindian City, Taipei County (臺北縣新店市中興路一段248號).
The reguirements for getting married can be found here
To summarize (I still reccommend you read the above document):
Application: NT$2 (the form to apply for the whole thing)
Ceremony: NT$1000 (weekends and public holidays NT$1500)
English marriage certificate: NT$400 each
Chinese marriage certificate: One included in the price, extras are about NT$20, but I can't remember exactly.
You need to prepare the following:
1) A certificate to prove you are single.
2) Copies and originals of you and your spouse's IDs (passport for foreigners)
3) Copies of your two witnesses IDs (or passports for foreigners)
4) You and your spouses name chops.
Regarding 1): I got mine by asking my mom in South Africa to apply for me. When she got it back, she sent it to the ROC office in Johannesburg (in South Africa), including a note to state that we needed them to stamp it. She then sent it to me here in Taiwan. I then got it authenticated at the MOFA (Ministry of Foreign Affairs) 3~5Fl Chinan Rd, Sec 1, Taipei (台北市濟南路一段2-2號3~5F).
I read that if you just get this from the South African office in Taipei, then you just need to get it authenticated at the MOFA (Authentication is free).
Regarding 3): These two witnesses have to be able to attend the ceremony, their names will appear on the marriage certificate.
Regarding 4): This means you need to choose a Chinese name. Note that any children you have will inherit the last name of the father, even though the name is just made up. I chose my wife's last name, as hers has meaning for her and her family, and I thought it was the best choice. You will then have to get a stamp made for yourself. This you will use on the day of the ceremony.
Once these are all ready, head off to the office (there's one in Taipei City, too, I went to Hsindien (Xindian)). You need to book an appointment to have the cermony. You have to book at least 3 days in advance. At this time you can tell them how many copies of the marriage certificate you want. I suggest you opt for at least one English copy and a Chinese copy.
Then arrive on the day, you have to put your chops on the certificates. Go through the ceremony and there you go, you're married.
Oh, you also need to go to the household registration office in your spouses registered town to make sure your marriage is put down in her household registration.
Second, changing your VISA
Next part in the process is to change your Visa to what is called a JFRV (Joining Family Residence Visa). This is not mandatory, but it means your stay is connected to your spouse, not to your employer.
Cost: NT$3000 (Americans: $NT4400)
To do this you will need:
1) A passport (bring it and make some copies)
2) An application form
3) 2 ID photos (2" x 2") (having more is good)
4) A marriage certificate (Chinese if you have one & make some copies)
5) Household registration (bring originals)
6) Police clearance certificate (original and 3 or more copies)
7) A health certificate (with stool test)
NOTE on 4): If getting married in Taiwan, the Taiwan marriage certificate is enough. If using an overseas one, you need to have proof of registration of the marriage, which then has to be stamped by the ROC office in your country, and then authenticated at MOFA.
I took so long to do everything that my original police clearance certificate had expired, so here is what I did the second time around (I never completed the first time).
Apply for the police clearance certificate. I did this at a police station in SA near my parents home. That took about 2 months to get back, some people never get them back, but if someone at the SA end keeps asking, it will come. After waiting for 2 months, my mother tried Police Headquarters in Jo'burg where these things are processed, but no one picked up the phone. She asked the local police station to help out, and they got it back in a week.
She then sent it to the ROC office in Jo'burg and got it stamped.
Then she sent it back to me.
I did this all by courier, so as to get the process moving.
NOTE: All documents are only valid for 3 months, which is why I recommend doing the police stuff first, as it might only get to you once all the other things have expired.
When you know the Police Clearance Certificate is on it's way, go get the health check. I went to Ren'ai hospital. Make sure it's a MARRIAGE check, which is different to the teachers' check. I had to give a stool sample, no big deal. This cost less than NT$1000, or in that region, take along your passport and a photo for each health certificate (usually 3 or so). It takes Ren'ai Hospital in Taipei it's 10 days till you can pick it up.
Also go get the "Household registration" from the local office that issues them (I just know where the one near my house is, so sorry no other details about this one). It's issued on the spot for a small fee (NT$20 each), I got 2, just in case.
When the Police clearance certificate arrives, take it to the MOFA, and get it authenticated there. You'll need to give them the original and 3 copies, take your passport along too. Processing time is 3 days.
After picking up the Police Clearance Certificate, you will have everything you need.
Take all the required documents and their copies to the MOFA, fill out the form, making sure to tick "Joining Family" as your reason for stay. Give them the stuff at the counter. Processing time is 10 days.
Lastly, the foreign affairs police
You now have 15 days to get to the foreign affairs police to get your ARC.
Cost: NT$1000 (They only stamped mine for 1 year, they charge you NT$1000 for each year they stamp it for. ie. stamped for 3 years: NT$3000)
Make sure you take:
1) Your passport with the new VISA
2) Your household registration
3) A photo (ID size)
Go back in a few days and get your new ARC.