To work part-time legally, you need to apply for student residency once you land in Spain. Once you have your residency and get a job offer, you take the offer to the police station and they will give you a new student residency card that states that you can work 20 hours a week (this goes on the back of the card). You have to keep renewing this when you renew your residency. You also need to prove that you have passed a full course load each year.
A lot of english teaching academies imply that anyone with student residency is working legally. But without having the proper work exception on your residency card (and paying taxes, social security, etc.) you are not really working legally. Of course, this is what most people do, because it's a bit of a bureaucratic adventure to get the proper paperwork.