As I don't know well others form of feudalism I will speak about french feudalism.
It really started with the carolingian in France but the final form will appear more or less in X-XIth century.
The basic is like you said giving a fief to someone in exchange for service, like administer it or coming to fight when called. If I remember well at the beginning only the king would distribute fief. The fief could vary a lot, some would administer a territory with a village, another a forest but it could also be something like make the coin (but since it something really important the king would usually keep this for him).
The fief wasn't hereditary and you could also loose it, if the father of a family had a fief and died the son had to ask the king to have it again and it wasn't certain either. Lord who had territory near the border of the kingdom began to give them to their soon without passing by the king and since they were in general strong territory defending the frontier, the king to avoid rebellion didn't act and just confirmed, thus, little by little it became hereditary.
The fief come with a pledge to your suzerain, which in exchange would accept to give you a fief (although in fact the suzerain has the tight to give nothing if he want). At the beginning there was a problem since you could pledge to as many people you wanted to recieve a fief each time, while it doesn't bother anyone in time of peace, when war start between to lord with the same vassal, the later had to choose between his suzerain which to join. To prevent this you had a suzurain who was higher than the other (in french it's called Homme-lige I didn't find an equivalent).
Since you had vassal with many territory to administer and they could be in all of them in the same time, those people would then give the task to some other people who would pledge loyaty and everything to them and administer the territory in their place. You have the big vassal who became suzerain to a couple of little suzerain.
Again it wasn't planned but since it was done and the king couldn't do anything it became an official rule. The feudal system grow a lot like this.
You had also some complicate case of vassal, for exemple the church could have a fief to administer but men of god can't fight so they can't protect it, right ? Then you have a dual system of vassalisation were the church and likewise a knight would hold the same fief but each with different task.
I think I said the most important point feel free to correct me as I did it from memory