Generally, the thing you will be most known for is your character class. An elusive thief, a valiant warrior, a devout priest, etc. However, there will be deeds that will stand out above others, and there also can be alignment fame (or infamy, if particularly evil or chaotic). Most basically, the character will be known, for good or ill, by what he is and what he does. Slay a band of marauding goblins -- fame. Burn down an orphanage -- infamy.
Here is a rough chart of the levels, and the amount of fame they correspond to:
| 1st-4th level || Relatively unknown. If of noble birth, it is extremely minor or hidden |
| 5-8th level || By this time has proven himself a hero/villain. Educated men and bards will know of his deeds, but he will not be widely recognized. |
| 9th (Name) |
| Known by all in his state/province. Can set up some sort of headquarters and attract followers. |
| 11th level || In/famous throughout the country. Could possibly have a place at court. |
| 13th level || Known throughout the continent. |
| Known the world over. His deeds will be spoken of in distant lands |
Of course, your fame/glory/renown/infamy could result in other actions being taken. Being known as an amazing warrior might have others challenging you for the title. Being infamous might mean a price is on your head, and so on. The player and DM are encouraged to be creative.