Tim B's answer is pretty realistic. Force is the true legitimation of power in a feudal society, our concept of legal authority is an anachronism.
That said just because people are illiterate does not mean that they cannot recognize symbols of authority. In fact feudal societies often have dense symbolic systems for non-verbally conveying each individuals place.
1) Historically specific colors became associated with rulers. For example purple cloth is associated with kings and emperors due to the high expense of producing pre-modern purple dyes. While the people of the town might not know who their king/lord is should he appear clothed in a color associated with royalty, they are more likely to accept his claim. Perhaps the color is associated with a particular royal family or lineage.
2) Legal restrictions on clothing items, known as sumptuary laws, are often used in feudal societies to reinforce distinctions. While historically this was used to distinguish nobles from commoners, there is no reason that a specific cut of clothing couldn't be limited to members of the royal family.
3) Objects can also legitimate authority. In the Roman Republic the authority of a magistrate was indicated by the number of lictors (bodyguards essentially) who they had at their command. Each lictor carried a ceremonial axe which symbolized their ability to impose capitol punishments. Any number of similar items (beyond the signet rings mentioned in the question) might symbolize power. While no one in the town may have seen these objects before, if they are sufficiently distinct oral traditions or art may make them recognizable.
4) Oaths tend to be very important in illiterate societies because of the lack of external confirmation. Should taboos against oath-breaking be strong enough, perhaps buttressed by any number of superstitions, then a strong oath might be sufficient for establishing ones' identity.
From a modern perspective none of these symbols may seem sufficient to prove someone's identity but the standards of evidence in an oral society are likely to be far lower than they are in a literate society. Therefore some combination of these symbols would likely help a lord or king to prove their identity at least until a higher authority (church leader, high noble etc.) could be consulted.