Yes, quite open for -skilled- workers and even more open to students. I emphasize the "skilled" part because trust me, you don't want to come all the way here to engage in low-skilled labor. Highly skilled work is already too life-consuming enough. However I don't know how the construction sector would be, it is the equivalent of the American military industry (i.e. that's where they will throw ridiculous amounts of money whenever they want to "stimulate the economy") and with the LDP winning the elections yesterday the pouring of concrete all over Japan will go back to usual.

If it is skilled work, I recall any undergraduate degree overseas plus a job offer are the main requirements you need to get a work visa. Yes, no need to wait for a space to open as is the case with the H1 visa in the US. And I think this year the process got even easier.

To get a contract, well, if you can speak Japanese then you are halfway there. If you can't, I can suggest:

1. The companies that seem to be hungry for IT/software engineers (judging from the amount of spam I get from recruiters), may take your from whenever you are, and where probably Japanese language skills are not important are: GREE, Rakuten, Amazon Japan. I think you can apply to those through their websites.

2. Message me so I give you a list of recruiting companies that seem to specialize in foreigners in Japan.

3. Some people recommend checking out www.gaijinpot.com from time to time.