Most quests can only be done once: you talk to the starting NPC, you do what they want, they give you your reward and the quest is done. However, there are some quests which can be repeated, and these are generally considered the easier (albeit boring) way to raise your fame. As you complete these quests over and over, your fame will slowly be raised by the successive completions. Some of the best repeatable quests are mentioned in the How To Level Up Fame section.

If you are intent on obtaining high levels of fame, it is important to understand how fame is rewarded within FFXI Gil. Some points to keep in mind, to clarify issues that are often confusing for new players:

Quests vary widely in how much fame they reward. Each quest has its own level of fame associated with it, so that if one character has done 30 quests and another character has done 30 different quests, they will not have identical fame.
The amount of fame rewarded from a quest is often based on it's difficulty. A simple quest that involves walking across the city to deliver an item will give a very small amount of fame. A harder quest that involves going out and killing creatures will usually reward a bit more. A quest that involves going to another city far away or takes many different steps to complete will generally provide the most fame.
Quests which require a high character level to complete give more fame than those which can be completed at level 1. While there are no actual level requirements for most quests, some quests involve going to high level areas and/or killing creatures that just can't be done by a low level character. These more difficult quests will generally provide more fame than the ones that can be done at low levels.
Your rank level has no impact whatsoever on your fame level. Your rank is raised by completing missions, which are started by the gate-guards in your home city. Your rank represents your political popularity, and is raised by the leader of your home city as you complete specific, sequential missions. Your fame is raised by the quests you complete, which are far more scattered and represent your common popularity with the everyday person on the street. Unlike missions, no particular quest is required to obtain a specific level of fame. (One caveat to this rule regarding ranks: some quests do require access to certain areas of the world that aren't initially available. That access is granted by having a certain rank, and so for those quests, your rank does matter. One example of such an area is the Chateau d'Oraguille in San d'Oria.)