0. Secure a Job
First things first, you'll have to secure a job with a Spanish employer. This means having a confirmation of employment and a drafted contract. Once you have this, your employer will have to start the employment procedures in Spain, while you patiently wait at home.
1. Obtain a Work Permit
To apply for a work visa you'll need a work permit. This is a document authorising you to work in Spain. You'll have to attach this document to your work visa application.
Your employer will have to apply for a work permit to the provincial office of the Ministry of Labour (Delegación Provincial del Ministerio de Trabajo e Inmigración) on your behalf. They'll have to prove that you are employable in Spain and will have to go through a few bureaucratic procedures. Processing work permits is something that can take a while so plan ahead. Work permits aren't exactly easy to obtain. Nevertheless several are handed out each year so it's not at all impossible.
2. Apply for a Type-D Work Visa
To enter the Schengen Area for purposes other than tourism and for stays longer than 90 days you'll need a Schengen Type-D Long Term Visa. You'll need to apply for this at your local Spanish diplomatic mission back home. When applying you'll need to provide the following documents, according to the Spanish consulate in Los Angeles:
DOCUMENTATION TO SUBMIT
Visa application form and visa Documents Checklist (Original and photocopy): The application form must be filled out in capital letters and signed.
One passport-type photo. See specifications here
Passport or Travel Document. (Original and photocopy of the main page). Passport should be no older than 10 years. Please make sure your passport has at least one blank page for the new visa.
I.D. Card that proves your place of residence is within the jurisdiction of the Spanish Consulate of Los Angeles (Original and a photocopy). You can provide one of the following documents: U.S. Driver license, State I.D. card, Voter’s Registration Card, current Student I.D.
(Non-US Citizens only) Alien Registration Card or long term U.S. Visa. (Original and a photocopy).
Holders of B-1 and B-2 Visas cannot apply in the United States; they must apply in their country of residence or country of origin.
Applicants holding Student Visas must also submit their I-20 signed by the university on the last page and a copy of their F-1 Visa.
Authorization of work and residence permit approval (comunicación de autorización de trabajo y residencia) issued by the Oficina de Extranjeros o Dirección General de Inmigración of the Ministry of Labor (Ministerio de Trabajo e Inmigración) in Spain. This document cannot be older than 30 days
Work Contract proving the fulfillment of minimal economic funds during time in Spain (Original and a photocopy)
Certification of “absence of police records” (18 years of age or older) (Original, a photocopy and a translation into Spanish): verified by fingerprints. This document is valid for 3 months in reference to the date that it was issued. The document can be issued by:
a) The State Justice Department (all states where the applicant has resided in the last 5 years) and the document must be legalized with the “Apostille of The Hague” by the Secretary of State of said state.
b) The U.S. Justice Department– FBI Federal Bureau of Investigation and must be legalized with the “Apostille of The Hague” by the Secretary of State of the corresponding state.
Medical Certificate: (Original, photocopy and a translation): It must be recent (Issued within the last 3 months), include letter-head and handwritten signature of a doctor (M.D. or D.O.) with the following format (Please see specifications attached)
Disclaimer duly signed
Payment of the Visa Fees is accepted with money orders. Money orders are to be addressed to the General Consulate of Spain Los Angeles. See the following link for fees. Money will not be reimbursed even if the visa is not granted or is cancelled.
3. Once You Arrive in Spain
Apply for a Foreigner's Identity Number
Once you enter Spain with your Work Visa, you'll have 30 days to obtain a Foreigner’s Identity Number (Número de Identificación de Extranjero) or NIE. This is a mandatory step. You can do so at your Local Police station which will also register the fact that you are staying in their jurisdiction.
Apply for a National Security Number
To work in Spain you'll have to register with the General Social Security Fund (Dirección General de la Tesorería General de la Seguridad Social – TGSS). Usually your employer will do this for you, unless you are self-employed in which case you'll have to do this yourself.