"Paella" really means literally pan, it's a derivate word from old latin language "patella", in italian "padella" and in french "poêle"... So, my theory is that it's an original type of pan from the old mediterranean cultures, in that there was elaborated food that then was not served in plates but people eat directly on the pan.
The first historical reference of which witness is had on the use of this type of pan in cuisine, was in the recipes book called "Opera dell'arte del cucinare" by Bartolomeo Scappi, the private cook of the Papa Pio V, in the XVI century.
The requeriment of this pan to make "paella" it's because the characteristics as well sayed @ptolemy, this kind of pan must be made with iron to obtain easy the Maillard reaction (the crispy base) and wide to facilitate the homogeneous evaporation and to obtain the dry effect. It's like if you want to do salted vegetables with an asian touch, well, you can do it in a current pan but surely the result is not like if you use a "wok"... I mean, some textures are only possible to obtain with the correct tool.
So... Like a knife, with the paella you must to take some cares because it fills with oxide easily, we apply a little bit of olive oil and hang it on a wall with some leaves of newspaper on the ground for if it falls some drop of oil..
I had never heard about not using onions in paellas and fideuas, that surprises me. I never used much but l always thought they add to the flavor.
Stefan
This one precisely is an old myth but really the authentic paella doesn't take onion because it tries to obtain a texture of hard grain (al dente), and the fact is the onion softens the rice. On the other hand, with "wet" rices onion can be ok, and the fact is that onion is in the base of some italian risotto, but they use "carnaroli rice" wich is so hard and for sure is good to soft it with a bit of onion.
Thank you for all the comments, I never thought that a paella was anything interesting more far than a curiosity and I meet that some of you even have your own paellas ... Wow.
Namaste.