I have never had the dubious pleasure of getting a working visa in any other country, and therefore I am not qualified to compare the efficiency of the Japanese system to a norm of any sort. However, I do not hesitate to say it's an overly bureaucratic process ensconced in gratuitous amounts of red tape, much like everything else in this glorious land. Observe:
Step one: Sponsorship
This step is applicable to most types of visas in Japan to some degree, but with a working visa, the sponsor will almost invariably be the company for which you will be working. All paperwork will usually go through the HR department, and immigration usually prefers to work with them instead of with you. This is both good and bad; less hassle for you, technically, but also a mild slap-in-the-face welcome to life as a foreigner in Japan. It's not so bad, really, once you get used to it.
Step two: Paperwork galore
You'll need to fill out several documents, which should be supplied by your company. If you have more than one job, it will infinitely complicate the situation (both in terms of immigration bureaucracy as well as everything related to your taxes, social security, and insurance – be forewarned).
Step three: first trip to the Immigration Office
You will need to haul your behind to the immigration office in the prefecture in which you live. It doesn’t matter which office is closer, and any defense you attempt to conjure up to warrant going to another office will be met with disdain and a lot of wasted time. For my fellow 神奈川県 dwellers, head to the 横浜 office (take the 東横線 to 元町中華街駅, exit 4, no matter what the website may say). For the unlucky ducks in 東京, you get to take a long bus ride from 品川駅 out to the office. Check the hours of operation carefully, and come prepared to wait a long, long time. I highly recommend headphones and boundless patience to tolerate the abundant noise pollution of screaming children.
Take a number and wait until it’s called. Once you get to the counter, hand over your passport, alien registration card (if you have one), and whatever documents your company said you should bring. If you’re really lucky, they’ll say everything is in order. If this is the case, they’ll give you a postcard and ask you to write your address on it. This will be sent to you when everything is completely processed and they’re ready to give you your actual visa. In the meantime, you get a stamp in your passport that says you’ve applied for a visa. This also means you’re not supposed to leave the country.
Step four: wait
They say it takes two to four weeks, but this is a blatant lie. In fact, I’ve waited up to two and half months in the past, and as little as five days on other occasions. It’s completely random. But nonetheless, keep an eye out for the postcard in the mail. Once you get it, you’re expected to go back to the same Immigration office by the date stamped on the card.
Step five: second trip to immigration
Go to the same office as before, and take your postcard and passport to the person at the appropriate counter. They’ll give you a number and some forms to fill out. In order to pay the 4,000 yen for your visa, you’ll have to fill out a Certificate of Payment of Fee form (手数料納付書, “tesuuryou noufusho”) and circle “change of status of residence” (在留資格の変更許可, “zairyuushikaku no henkou kyoka”) and then buy a revenue stamp (印紙, “inshi”) worth that amount. These are usually sold in the same building as the immigration office, or you can buy them at most convenience stores. Buy the stamps while you’re waiting for your number to be called, stick them to the allotted space on the form, and continue waiting. However, before buying the stamps, take note:
To kill two birds with one stone, I highly recommend applying for a re-entry permit (再入国許可, ”sainyuukoku kyoka”) at this stage in the visa process. If you plan to leave Japan, they’ll confiscate your registration card at the airport unless you have one of these. If you get it now, it will save you yet another trip to the now-familiar office. In order to do so, fill out another Certificate of Payment of Fee form, this time circling “Re-entry into Japan.” You can choose either a single re-entry permit (3,000 yen) or a multiple re-entry permit (6,000 yen). This depends on how often you plan to travel throughout the duration of your visa. If there is any chance that you might leave the country more than once, get the multiple re-entry permit now instead of having to buy several single re-entry permits. You’ll thank yourself later.
Once all your documents have stamps, after you've waited forever and your number is finally called, they'll take the certificates and give you your passport complete with two identical orange stickers: one if your visa, and the other is your re-entry permit. Treasure them. You're legal (almost).
Next step: Registration
If you haven't already done so, you’ll need to get your alien self registered. After registering, you’ll be notified of something called Japanese National Insurance (国民保険, “kokumin hoken”), which all people living in Japan are expected to have. However, if your company will be enrolling you in Japanese Social Insurance (社会保険, “shakai hoken”), you don’t need the National stuff. Don’t pay for both!
From now on:
Depending on the type of visa you were given (1 year, 3 year, or 5 year), you’ll have to repeat the visa process every so often. Yes, you have to pay 4,000 yen for visa extensions in the future, as well as 3,000 to 6,000 yen for a new re-entry permit. If you change your job and therefore the sponsorphip of your visa, you will need to go through a completely different yet similar process. And don't forget to always register every visa extension, update, or other change to your address, job, or personal life with your ward/city office and have it recorded on your registration card. Enjoy.