Electronic – arduino – Combining Arduino and LEDs on same power channel

I would wire up a Power N-FET, that could handle up to the full 5A and 12V across it, wire it in series between the LEDs' common-cathode and the GND, and pulse-width-modulate its base using the Arduino to control the brightness. That will give you the illusion of dimming, as brightness is a function of the average current experienced by the LED, and the physiology of the human eye will take care of the rest :).

Do you have the DC supplies and Arduino grounds connected together? If not then any PWM from the Arduino will not work.
Most small plug type DC supplies are floating, so their grounds will not be connected to USB ground (of course the USB ground may be floating if e.g. on laptop battery)

As Russell mentioned a diagram of your connections would be useful.

Thanks for the diagrams:

Your problem is as stated above, you need to connect the grounds together. Otherwise, the Arduino PWM signal has no return path (remember a voltage is always relative to something) to Arduino ground since the grounds are not connected.
It's okay to connect all the grounds together (arduino and DC supplies)
The only time is isn't is in the very rare case where you might have a supply "ground" that is above earth ground relative to supply grounds (e.g. a 20 V supply with V+ at 50V and V- at 30V relative to earth/AC ground could not be connected to a 20V supply with V+ at 20V and V- at 0V)
If in doubt you can test for any voltage between the grounds with a multimeter (e.g. one probe to one ground, one to the other ground) but since most DC supplies are floating (not referenced to earth ground) then essentially the outputs are just like batteries.

Hope I haven't confused things here :-) Connect them together and let us know how it goes. Here's an altered version of your diagram (note extra black ground lines):