It is possible to control brightness of an LED strip (connected using a relay and having a seperate power supply ) using output from an arduino? The circuit contains a relay interfacing with 12v power supply and LED strip. Can the brightness for this strip of LEDs be controlled using the analogWrite command? 
This works perfectly for a single LED, but when i replace the LED with a relayed LED strip with its own adapter, it doesnt produce any perceivable output
As Gerben said relays are only for on/off control. If you need to fade led you should use transistor. 


What kind of transistor?


It depends on power consumption (how many LEDs).


How to connect Arduino, LEDs, transistor?


This is schematics how to connect the strip. As i assume resistors are already on the strip.



And little bit simpler image :)