Well, after messing around, I think I half understand how it all works. Much of the workings have already been explained, but I hope to add light.
Here are the general principles I gleaned. I'm open for correction:
1. Renown is just a tie breaker. All you need is to have more renown than the next nobleman in line for the fief.
2. Who's the next nobleman in line? first, it's the guy with no fief. If everyone has a fief, then the next noblemen in line are the ones with with only 1 fief. Then the fief probably goes to the guy with no more than one fief AND has highest renown among the 1 fief owners. Likewise, if everybody has at least two fiefs, then the next in line is probably the guy with 2 fiefs AND highest renown amongst the group.
A side question is: Does a city count for more than a town? Maybe. I haven't tested enough to see. A possible answer is that 1 city = 3 towns in the bid or perhaps it's just as simple as 1 city = 1 town for the bid.
3. The # of positive relationship points with the king is probably irrelevant. Do nobleman have some code-hidden relationship with the king? probably not. If so, then I doubt that this factor is included in the "who gets the next fief?" algorithm. Anyways, this didn't seem to be a factor in my experiences.
It's possible that renown and relationship combine for the tie breaker score. But I doubt it.
Here's some ramblings about my experiences...
I did some messing around with a city siege (save/load) At first, the king gave the city over to a lowlife without any land. After many game loads, the king did the same thing over and over again...he gave it to the same nobleman. I loaded the game (before the city) and took a castle so that the lowlife nobleman could have some different land first. Now that this nobleman had his fair share of land. I tried taking the city again. This time the king gave it to a nobleman who had a town and 4 renown higher than me. I re-loaded, and made sure I had just enough renown over the next-in-line guy. Sure enough! The king finally awarded it to me.