Arduino-controlled slot car set - Why are my MOSFETs burning out?
I see a couple of things here; none directly obvious as the culprit.


How much current are you drawing from the slot car? It's hard to say whether the MOSFET (and your wiring, for that matter) is going to handle it OK.
Does the Arduino output 5V logic levels or 3.3V? Both parts sold by Sparkfun are 5V logic level MOSFETS -- shame on Sparkfun for saying -


  This is a very common MOSFET with very low on-resistance and a control voltage (aka gate voltage) that is compatible with any 3-5V microcontroller or mechanical switch.


because it's not compatible with circuits that output less than 5V. If you have a system that outputs 3.3V, you need a MOSFET with on-resistance specified at 3.3V. 
The freewheeling diode between MOSFET drain and the power supply is to protect the MOSFET, not the motor, from inductive voltage "kickback".
Keep your wires short! They add unnecessary resistance and inductance.
Breadboards are questionable for currents over 100mA; I'd keep the power supply wires off the breadboard and solder directly to the MOSFETs.
Yes, a heatsink would be helpful; that may be your problem. If the tab of the FET is too hot to touch, you probably need a heatsink. There are some easy clipon heatsinks at Digikey that are &lt; 50 cents. Here's one: 591202B00000G. 
I always put a resistor between microcontroller output and the MOSFET gate; it prevents oscillation due to inductance, and it prevents damage from propagating back to the microcontroller. (see my blog entry for more info)
I always put a pulldown resistor to keep the MOSFET in a defined state during reset.
grounding: The connection between microcontroller ground and MOSFET ground is critical; if you add inductance here, that can cause poor turn-on or turn-off in the MOSFET. Keep this short, and if you can't, then you may want to use a MOSFET driver located right at the MOSFET.