Most of the part-time jobs in Japan require basic Japanese skills, this can be an issue if you are new to Japan and a beginner in Japanese language.
In my first year in Japan, I found it very hard to even communicate in basic Japanese that made it hard for me to find good part time jobs. Based on my experience, these are some common points to note when you are looking for part time jobs:

1.Platforms like “GaijinPot”, “Mynavi Baito” help you to find part time jobs based on your requirements like type of job, Japanese ability, place etc. You have to create an account and upload your resume and other details to apply.

2.Direct inquiries at local convenience stores/ restaurants/ shops. In fact, my first part-time job was at a convenience store. I directly inquired to the staff if they are recruiting any part-time employees. They connected me to the store head (called “tencho” in Japanese). I scheduled an interview and voila! Joined as a trainee. 

3.Asking friends and seniors is the best way to get a part-time job as they can introduce you to the recruiters directly and guide you through the initial days of the job. 

4.The University of Tokyo provides several On-Campus Job opportunities, if you want jobs that don't require Japanese this is the go-to place to find it !