The constitution forbids labour for children under 15 full years (except for work in movies or theaters) as well as restrict the work for children under age 18 to light labour that is not dangerous or harmful (Source).
Apart from that the schools can have their own custom regulations like banning jobs.
Regarding the schools motivation:
Students who wear a certain school's uniform are regarded as representing their school to the outside world. Therefore, most schools really impress upon their students that they have a duty to behave well outside, as emissaries of their school. And as high schools are very competitive and take their institutional reputations very strongly, that can mean a lot of pressure for those kids to stay in line. Many of them worked really hard to get into that school, after all.
And so, yes, some schools do ban their students from having part-time jobs. The school wants the kid to study, and take part in school clubs and sports teams. If they get a job at McDonalds or something, suddenly that job becomes their identity, not being a student, and as far as the school is concerned that can only be a bad thing.
Many students who need/want extra spending money do try to get around that rule. In a big city like Tokyo, it's easy to just try and blend into the crowd. But, as has happened in many school life anime over the years, it only takes one person recognizing you to blow your cover.
For whatever it is worth this PDF of a 2006 survey states that 40% of the high school students have part-time work experience (Page 4). So either not many schools have those rules or the students broke them.