I started pretty early with Rebecca... maybe like 2-3 months, and she started using her signs at about 9 months. And then she was still communicating mostly with sign when Elias was born, so he started at birth (and signed later than she did... I think around 12 months), and he is still communicating with a lot of signing, and minimal speaking.

I don't think it is ever "too early" to use signs, but I do think they pick them up a lot faster around 6-12 months than they do at 1-6 months.