MOSFET controlled DC motor too slow

You want the negative end of the 5V supply (let's call it ground) connected to your MOSFET source, not the drain.
To turn on, you need to apply a voltage between gate and ground, 3V should work okay for most small MOSFETS. You would need to connect the negative side of your 3V to ground (i.e both 3V and 5V negatives tied together) and positive to the MOSFET gate.

Alternatively you can just apply 5V to the gate (the same 5V used to drive the motor)

Also, if you are just touching the voltage to the gate (i.e. not driving with uC or something) then you will need a pulldown resistor between gate and ground to make sure it turns off when power is removed. Something like 10k will do (if you don't have that value, try anything between say, 1k and 100k)

As Faken mentions, a reverse biased diode across the motor is needed to prevent the voltage spike on switch off destroying the transistor. Connect e.g. a 1N4002, cathode to V+, anode to MOSFET drain.

For clarity, here is an example circuit:

Your motor is driven from 5V, so you just put your supply where the 9V supply is. To drive you apply a voltage (above MOSFET turn on) to the gate (FROM MCU) Check your datasheet for the turn on voltage, but 3V or 5V should probably work fine (note with part number shown more than 3V will be needed for reasonable turn on)

Under electrical characteristics in the datasheet, you are looking for a graph like the one shown below. Along the bottom is the drain-source voltage, along the vertical axis is the drain-source current, and each line is a different gate voltage.

Your drain source voltage is 5V. We can see if we apply 3V to the gate we will only get around 30mA, as the MOSFET is not turned on fully. Raising the gate voltage to 4V we will get around 400mA, which should be enough to drive a small motor. Note that the maximum drain source current is only 200mA for this part, so you need to make sure your motors current rating is less than this. If you need more than this then the part shown is no good.

If you give details on the MOSFET and motor used (part numbers, datasheets) more detail can be given.

I see a couple of things here; none directly obvious as the culprit.

1. 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.

2. 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.

3. The freewheeling diode between MOSFET drain and the power supply is to protect the MOSFET, not the motor, from inductive voltage "kickback".

4. Keep your wires short! They add unnecessary resistance and inductance.

5. Breadboards are questionable for currents over 100mA; I'd keep the power supply wires off the breadboard and solder directly to the MOSFETs.

6. 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 < 50 cents. Here's one: 591202B00000G.

7. 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)

8. I always put a pulldown resistor to keep the MOSFET in a defined state during reset.

9. 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.