I have a 12V 3A adapter, this feeds the arduino and the ledstrip. The ledstrip got a IRF44Z mosfet for each color. It's wired up like this :http://www.ladyada.net/products/rgbledstrip/
The total current draw is about 1A when the strip is white.
The strip itself is a 30 leds per meter low power consumption one.
@Cranium: It seems you were spot on. Brought a +12 wire to the other end of the strip and the gradation problem is solved. Now I also know why all these strips are 5m at max everywhere :-)
You should be using a logic-level MOSFET, the IRF44Z needs 10V gate drive to turn fully on - this probably means its running hot and not delivering the full 12V to the strip.
To be fair (and this quite surprised me) the LadyAda tutorial recommends a MOSFET that isn't logic level either!
If you are driving a MOSFET from 5V you need one that has Rds(on) specified at "Vgs=4.5V" in the datasheet. Most TO220 packaged MOSFETs are not logic level, note. Also these days there are cheap MOSFETs with far better specs than the one's from the 1980's!!! Look for Rds(on) < 0.02 ohms if you can, it'll run cooler.
Also my standard warning - ignore the current rating for MOSFETs, that's not useful information. Go by the Rds(on) value and calculate the power dissipation using I-squared-R. If you want to run without a heatsink the power dissipation should be less than 1/2 a watt, preferably even less. Since the power is proportional to current squared, higher currents rapidly lead to "issues" and using a "10A MOSFET" for handling 5A is never sensible, you want one rated at 0.02ohms or less for 5A, 0.005 ohm or less for 10A, or you'll need heatsinking, fans etc.
For example here's a logic-level MOSFET: http://www.sparkfun.com/products/10213