The special ingredient of paella is saffron (as everybody else already confirms).
The best way of preparing saffron for your paella is to soak it in warm water at least 30 min. before you add it to any dish. Take care not to mix it with your broth as you are not going to use all of it. When the rice is ready to be cooked, first add one measure of boiling broth, then add the saffron infusion, then add the rest of the broth you need to measure out.
When buying saffron, look for threads, those are the stamps of the flowers. Don't buy the saffron powder. The powder is cheaper, but you can't be sure it wasn't adulterated. Saffron is very expensive, as it's very labor intensive.
Really real paella is cooked on vines. That will give a smoky flavor. But I don't think you'll find that in a restaurant.