Welcome To Podunk!
When your party comes to a new area as relative unknowns, they're not going to get much access. Only by proving themselves in various ways will they begin to be known.
This system helps reflect that progress. It is most useful when the party is going to spend some time — even just one level — in an area. It's less useful for areas that the party is just passing through momentarily.
When you arrive in a new area, you have no reputation. As you accomplish things in the region, for the people, you gain reputation, and gain access to more reticent and rarer individuals.
This is represented with a reputation star: $\star$
To begin with, you have no stars. As you complete quests, you will gain stars, until you have the maximum for the region.
As you accomplish quests and gain stars, your reputation increases.
Without any Reputation Stars, you can still talk to those who must deal with the general public, or those who are open to dealing with them: merchants, mostly, but also especially friendly, outgoing, or desperate townsfolk might be willing to chat with a complete stranger. Certainly anyone in the market for mercenaries, or anyone selling weapons, armor, magic, or lodging, would be candidates for conversation. But don't expect to be able to talk to just anyone on the street.
$\star$: "Howdy, stranger."
With one Reputation Star, you become well-known to a small group: those you have helped immediately, and perhaps their immediate friends and family. You're not a total stranger, but you're just beginning to get known.
$\star \star$: "Hey, it's those guys!"
With two stars, you are known to a slightly broader group. Many folks in the area have heard of you, or know someone you may have helped, but you're still an outsider. A helpful outsider, but an outsider nonetheless.
$\star \star \star$: "They're good folks!"
With three stars, you are generally well-known in the region, at least by reputation if not by direct interaction. Folks have probably heard of your exploits and your deeds, and even busy folks might make some time for you.
$\star \star \star \star$: "They're an asset to this town!"
With four stars, your group becomes admired in the region, well-known as a group to be relied on and trusted. Even the rich and powerful may be inclined to make time for you.
Not everyone in town is going to come up to the newly-arrived heavily-armed strangers and ask them to rescue their daughter. Your party must generally earn that trust, by building a reputation of doing deeds first. Various quests in town will have star prerequisites, meaning you can only gain them with a significant reputation. Some will not: you can have those even if you're new to town. The rewards for a quest will also increase as the party gains reputation.
Quests with no stars are generalized mercenary work: kill X goblins, defend caravan Y, etc. The rewards are scant and the risks are great, but the people generally have no reason to trust you, necessarily.
The people you previously helped out begin to entrust you with bigger problems, requiring a more daring solution. They are also more willing to part with important heirlooms and items as a reward.
Strangers may approach your group, having heard of them, to tackle knotty problems with correspondingly more impressive rewards.
$\star \star \star$
Important matters in the area begin to come to you. Major problems are yours for the solving, and major rewards yours for the taking.
$\star \star \star \star$
The entire town marshals behind you. They pool their resources to give you rewards for helping everyone with their major life issues.
The way to gain reputation is to do quests that match your star level until you gain a reputation star.
Now, depending on the size of the region, you may have to accomplish more quests to have a bigger impact. A town of 20 is going to be quickly impressed, but a country of millions will not be so easily persuaded.
One way to govern this is to start with a basic formula: for every two quests the party completes, the party gains one $\star$.
These stars only apply in a community of about 20-50 individuals. A larger community is made up of multiples of smaller "neighborhoods," so that once you achieve $\star \star \star \star$ in one community, you may need to do it again in another.
In 4e numbers (with 10 encounters per level), this means that the party reaches $\star \star \star \star$ with the community just before they gain a level: the last two quests they undertake in the community will give them the level up, and they will be heroes of the community.
This means you can easily flow through a game of 30 levels, simply by having 30 communities, with 60 quests per community. You can combine some of those communities into bigger towns and cities rather elegantly.