The main general rule is that you are taxed on where you are living unless there are extra considerations, including for example bilateral agreements of the countries involved.
Since this can get confusing and complex very quickly the two most common solutions for this problem I usually see are:
If the company has a subsidiary, a sister-company, or anything similar in Spain, then they essentially transfer you to this company, and will be employed by them. You'll get paid by a Spanish company and pay taxes in Spain.
You become a freelancer, and work for them on a contract basis. You send them invoices which they should be able to pay easily, and you are responsible to fulfil all tax obligations in Spain on your own. They should obviously pay you contractor rates, as they won't need to pay taxes and similar towards your employment anymore. Also since they are going to be a foreign company some local tax rules that are aimed to discourage people becoming contractors (like the IR35 in the UK) will not apply.
If none of these options is acceptable then - although you are never crossing the border physically - you are still a cross-border worker, as your residence is different to your employer.
Unfortunately EU rules are not too helpful in this case because:
Taxation and cross-border workers - no special Community rules exist
In the field of taxation there exist no rules at Community level regarding the definition of cross-border workers, the division of taxing rights between Member States or the tax rules to be applied.
The main recommendations are that you should not be worse-off tax wise than either a resident-worker of Spain or a resident-worker of Germany. The recommendation also suggest that if you earn most of your income (>90%) in a different country that you are resident in, those countries law should apply. However this is just a recommendation and not a global EU law, and cross-border tax laws are still bilateral between the various member states, if they actually have them.
Social security wise the answer is a bit more clear:
- If you pursue a substantial part of your activity, at least 25%, in
your country of residence, you will be covered by the legislation of
that country.
- If you don't pursue a substantial part of your activity
in your country of residence, you will be covered by the legislation
of the country where the registered office or place of business of
your employer is situated.
- If you work for several employers, whose
registered offices are in different countries, you will be covered by
the legislation of your country of residence; even if you don't pursue
a substantial part of your activity there.
- If you are self-employed
and you don't pursue a substantial part of your activity in your
country of residence, you will be covered by the legislation of the
country where the centre of interest of your activities is situated.
- If you pursue an employed and a self-employed activity in different
countries, you will be insured in the country where you are employed.
This also says that you should be covered social security wise in Germany, unless you start working in any other country as well, in which case Spanish laws will apply.
From my experience however most companies (who are not already having cross-border and/or remote workers) are not accustomed to the extra hassle, and just ask the employer to become a freelancer effectively pushing the extra tax complexity onto the employee.