I just about fly out of Newark every year for Europe, mostly London Heathrow.  Since they have to get a crossing clearance / track / time slot, do they get a certain amount of priority on departure so they aren't sitting and burning precious fuel?  How does that work?

The track "slot" time (there is actually no such thing) is based on the flight plan, but it is a very dynamic thing and things do change... you are certainly not given priority because you are on a NAT route.

Once you are on the way, within a certain time frame, you ask for your oceanic clearance and they try to slot you in as requested in the flight plan generally.

In addition, there are flow management mechanisms that analyse IFR flight plans and ensure that capacity -- either of the arrival airport, or ATC sectors enroute -- is not exceeded. For flights that pass through European airspace, the Eurocontrol CFMU (Central Flow Management Unit) analyses IFR flight plans and calculates a departure "slot" (CTOT -- Calculated Take Off Time) designed to minimise the air holding delay and to ensure that the volume of traffic enroute in any given sector is within the capabilities of the controllers.

 

In this regard, you may get a slot delay if there is lots of traffic expected on your route at your planned level. If it's a big delay, sometimes resubmitting the flight plan with a different requested cruising level or with a different route will yield better results but not always -- it depends where the restriction is (if it is a particular sector that is overloaded you could avoid it with a re-route or change of level -- but if it's the arrival airport that's over capacity then there's not a lot you can do).

 

However, once you've been issued your CTOT it's largely up to you as the pilot to do what you need to do to get to the holding point on time (remember it is a takeoff slot, not a pushback slot!). If you miss the slot then you will have to request a new slot, which could be significantly (hours, in some cases) later if you are unlucky.