As wiggy says, it'll vary by country. After 1 January, unless you're already resident in an EU country by then, and unless the UK and EU make a deal that covers this area, you apply or a work permit from the indivual EU country where you hope to be employed - or your prospective employer applies for you.
Work permits - Your Europe
What are we gaining out of this? Some bloody fish.
Yes, well, don't forget that those bloody fish are equally desperately politically important to a few EU countries, especially France, or they wouldn't be such an issue in the negotiations.