With the exception of United States and Eritrean citizens (unsure on second) tax status from employment (and other sources of income) is (usually) based on residency. The previous answer calls this "gainful residence". So if you are resident in the Netherlands you pay tax and social security there. To be clear, as the other answer (+1) has stated this will be your worldwide income.
The difference for US citizens is that they must still file tax returns to the US. In my case for example I am British, live and work in Switzerland so I pay all tax to the Swiss authorities and am declared nonresident with HMRC. To explain how this also affects me, if I were rich enough to own property in the UK I would have to pay tax on this to the Swiss authorities. Rental earnings should there be any would also be taxable in Switzerland.
Of course it is more complicated working for a firm in a different country. In particular:
- If the company has an in-country subsidiary the simplest route might be to be employed via them.
- If you are still employed via the UK your company will still make deductions according to this page. You will then need to declare yourself nonresident with P85.
- You may need to settle how you deal with pension contributions. You can make voluntary NI payments while abroad. However most EU countries have exchange agreements with the UK whereby contributions to local obligatory state pension systems can be exchanged should you return to the UK.
- You should also look at local income tax rules and how this will apply to you. You will almost definitely be liable for local income tax; there may or may not be gotchas locally to consider (there are for example in Switzerland).
Another option people often consider in this scenario is to become self employed. depending on the country in which you are resident you must be careful with this. The UK has IR35 for this purpose: contractors who look and smell like employees are taxed like it. The Netherlands appear to have a similar rule.
Finally you must also consider currency as an issue. Inside the Eurozone Euro-Euro bank transfers are done through SEPA which limits fees even "internationally". This will not apply for sterling - euro transactions. Your company might be able to handle this for you or may wish to pay an account in the UK.