Generally I look at what would influence the reputation of the party or an individual member of that party. What deeds are done, and how is knowledge of those deeds spread? In the current game I'm running, the group has done a number of very public things, done a few things for people in power, done things in the presence of people likely to talk to others (servants, merchants, travelling musicians). A few people have a very recognizable 'look' about them, and a couple carry virtually unique magic items with very visible effects. The accumulated baggage of all this is that now as they enter the realms of 10th level or so, sometimes they'll encounter things in the region that will exclaim 'Oh %&^*, it's them! Run!'. And they also have the attention of a few things that are thinking 'If I get rid of them, then my rep is made.'. Or 'They could prove to be a thorn in my side, like they were to X. I need to have them killed before I begin implementing my plans'.