Asegúrese de que está usando la función
analogWrite().
Estrictamente hablando, hay un par de formas para variar el brillo de un led -No sólo con Arduino-:
1) Variar la corriente que le llega al led
2) Usar PWM para controlar el led
En el sitio de Arduino hay un par de ejemplos, basados ambos en analogWrite()
http://www.arduino.cc/en/Tutorial/Dimmer
http://www.arduino.cc/en/Tutorial/Fade
PD. Para poder ayudar más, si quiere, muestre el circuito y el código que está usando.