FASA Games, Inc.

I believe it depends on the individual as well.
A host can be nice and provide all needs for those he like - from food to starships.
For someone who he/she dislikes, well, maybe a place on the barn with the horses will be fine, and a for a meal, old bread and water from the rain.

In advance also can be used if the guest wants the pomp of dinners and parties in their honor. If something more discrete is needed, a warning a few hours (maybe days ahead) or just showing on the spot would be fine, IMHO.

Proof of lineage is hard when you don't have a DNA scanner available.
But my guess someone could call the lineage (son of A, daughter of B, grandson of X) or some great dead it did and which it is known in the noble circles - from simple things (riding a horse at 2 years old) or complex (won a duel against four other nobles).

Gossip networks should be helpful, since many nobles enjoy the gossip.

There's a section in the revised player's guide about noble hospitality. But essentially, it boils down to you have to be a good host but the visiting noble must also act following a certain decorum.

Hospitality is important between nobles because of the importance of good political workings. If your Noble House is much more powerful than their noble house then the relationship of Hospitality is slanted. If you are of a house that the noble family is dependent on then they will offer you a great deal of hospitality. For instance, if you're a decados on the outs with your house and you go to the one petty Hawkwood landholder on Severus they will give up their own bed for you then again they'll also lay out a feast for the Decados that come to hunt you down. If you're a Trunsikon knight travelling in Li-Halan space and show up at a Li Halan Duke's residence he would get to have small talk and tea with a member of the Duke's family and perhaps the Duke would shake their hand if he can't find a decent excuse but then you need to go.
The greater enforcer of etiquette is what you have to offer. Hospitality is offered more freely and more generously to family because that bond is much more reciprocal, especially to family from another planet as nobles travel and need those connections. Likewise Noble's with power on planets where you do business are going to be shown lavish hospitality in hopes that your reputation will flourish or opportunities for trade will bloom out of your hospitality. Lastly I think there are some nobles that are just sticklers for etiquette. They will extend hospitality out of the letter of the laws of good manners even when it doesn't benefit them. However they are very specific about the limits of hospitality.

I actually think that Nobles routinely push the limits of Hospitality by staying too long or asking for boons that are too expensive. Perhaps that could be the basis for a nice little story, convincing a noble to move on.