International students get permission to work as a parttime work only when it is clear that working is not adversely effecting studies. Students have to enrolled in class As a part-time work, students are only allowed to work only 28hrs/week during classes and 40 hrs/week during the holiday. Part-time working permission can be obtained at the airport who are entering to Japan for the first time as a student. I will recommend you to make this in Airport Otherwise you have to go several time to the Immigration Bureau.You may have to wait for a several weeks and sometimes a month.

see this link for Rules for part time job in Japan.

We can find many Employement Magazine and newspaper ads which help us to find a job.A magazine like Townwork can be found everywhere near convenient store,Train Station and others public places.All Employement Magazine are free of cost. All you need to do is just search a suitable jobs for you and make a call.Check TownWork on web.

Haken　khaisya is basically a big companies which provides part-time jobs like cleaning,eventstaff,hotel staff,factory staff etc.. You can find so many jobs which do not need any Japanese skills but it may be little hard.If you have a good Japanese skill,you will get a good jobs.
Haken generally pays900-1200 depending on your job type.Working in night shifts get you more then working in day. If you are a newcomer,i recommend you to find Haken Companies and do a part-time for a while.After you get along with Japanese language and culture, it will become easy to find your dream job. During my studient period,i worked on Izakaya and Convenient Store as a part-time.It helps me alot to speak Japanese.

If some of your friends,classmates or relatives are already living in Japan or Working in Japan,this will make you easy to get a job. Be sure to follow a different ruleswhich helps to make a good reputation.

It may be little strange but it is better to ask for a job rather then sitting doing nothing.There is always vacancies in places like Convenient Store,Family restaurants, food factory etc.Once my friend went to Japanese restaurant for a drink,he manage to talk with the boss()and ask if there was vacancies or not. The boss told him that he was happy to hire him but he have to confirm about the necessary procedures and the date for interview. He got a call from the boss within a few days and he was asked to come with necessary documents.
So guyz dont be shy there is a lot of parttime jobs waiting for you.But be sure not to work in illigal places. There are so many things which we cannot learn just by reading or writing.Interacting with people helps to make you more confident and helps to increase your Japanese ability.