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?
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 :)