Firstly you can usually ignore the current rating as power-dissipation is the limiting factor (without substatial heatsinking).
The key spec is the Rds(on). Calculate the power dissipation for your load with P=I^2R. For large currents you are likely to want a heatsink (say if the dissipation is more than 1/3 watt.)
Secondly beefy MOSFETs have high input capacitances. Very high input capacitances. You can drive the gate from the Arduino with a resistor to limit the pin's current to a safe level for the microcontroller (say 25mA max - 220 ohms). However this means slow switching (many us) leading to a large power-dissipation pulse in the MOSFET while it switches. For low to medium power loads at low to moderate PWM frequencies this is fine, but driving a high powerload at high frequency PWM this will become prohibitive.
Arduino default PWM is 1kHz or 500Hz depending on the pin, so this isn't too big an issue unless you change it.
If you want faster/more efficient switching you need a MOSFET driving chip to charge/discharge the gate capacitance quickly (drivers are usually 0.2 to 1A or so). I've used a MIC4422 before which can drive pretty much any MOSFET hard from a simple logic signal. These driving chips need proper decoupling (but can level shift from 5V to 12V to allow non-logic MOSFETs to be used)
There is one more issue you need to be aware of which is capacitive coupling between drain and gate. For high voltage loads the voltage swing in the output can couple to the gate strongly enough to require that the gate is driven by a low-impedance source (a few ohms) to prevent voltage spikes on the gate (these can damage the gate oxide and whatever is driving the MOSFET)
The more voltage and current being switched, the more important this is. I would recommend for high current loads over 20V or so to always use a MOSFET driver chip to prevent this being an issue. Also logic-level MOSFETs are more sensitive to this problem.