Generally speaking, most companies will ship you to Japan first, bring you on board as a trainee or intern and then apply for your visa. This can cause problems. Things you should watch out for are them deducting taxes from your pay check (income tax etc.) which they cannot legally do, and begin registered as a company employee before you have your visa. Both suck, the first one you lose some cash that is rightfully yours, the second you risk being deported. However, put both together and you get to go on the immigration officer's short list. Fun, huh?
To get a working visa in Japan, there are several things that need to happen. A company or individual will have to sponsor you, you will have to apply for permission to be a resident in Japan (simple background checks), and if you are already in Japan you will have to leave the country to receive your visa (actually to change your status). For a bare minimum the company should sponsor you and help with your paper work. NEVER rely on them completely though. I almost got screwed and you might too. Know the procedures for applying and receiving visas. Ideally they should hold your hand and help you out, but who said this is an ideal world! Things to watch out for: your employment status at the company and whether your application is proceeding as planned. (the application procedure can sometimes take up to 3 month, and guess what, your tourist/training visa is only good for 90 days ... do the math.)