The Reputation shows you how respected you are. You can check out how you are viewed by each one of the four factions and by single cities. If you want to gain reputation in a faction then the best way is to complete missions for them (if possible) or pay them (e.g. bandits). A reputation in a city is increased by completing quests from post office, city hall or by transporting passengers - but only the legal transports count, for illegal you lose your reputation. A high reputation is required for more complex (and better paid) missions but there is more to that. A neutral reputation is required if you want to make a newspaper subscription. A higher reputation level is necessary to use other services (e.g. participating in an auction, using bank offers, recruiting people from a given faction). Notice that when it comes to transport missions they don't have to start from a city in which you have low reputation - this city has only to be your goal (both sides reward you with reputation points). Reputation also has influence on lowering prices in those cities in which you are liked.
Hint: you should work on reputation from the beginning of the game and focus on it a lot. In later parts of the game it is harder to do that (or it can cost you money). You must be very cautious and avoid making enemies with any of the armies - you won't be welcomed in their cities.
Factions: Bandits and Natives
There are four factions in the game: Bandits, Natives, Confederates and Unions. You can have good relations with all of them or you can select the one that you want to support while being a hindrance to others. A good idea (especially in the beginning of the game) is to be an ally to all factions or, at least, have neutral reputation.
Bandits - an alliance with them allows you to visit their camps in order to trade, you won't be attacked as much, you can accept missions in Saloons to transport contraband and missions to transport wanted people (during nights). They can be found almost anywhere, especially around big cities (Pittsburgh). Relations can be worsened very quickly: by attacking them (also those that are wanted) or being caught with contraband which is a goal of smuggling missions. If you want to have better relations you must complete their missions with success but you can also pay the bandits, when you are going past their camps, to gain reputation.
Natives - they are similar to bandits, the main goal to meet with them is to trade and they can also attack you. The difference between bandits and Natives is the place in where you can find them (e.g. areas near Indianapolis). They also don't have any special missions for you, although some side missions can increase your relations with them. Otherwise, increasing your reputation is done by money.
A good way for increasing your reputation fast is to find an enemy outpost on the map (preferably an outpost where Natives want to rob you instead of trading with you or in the case of bandits: passing by people with wanted letters) and each time you pass them by you must pay them to increase your reputation. It is not a good idea when you look at it from economic perspective but if you have a little bit of money then this way is the fastest and safest.
Unions and Confederates
Unions and Confederates - the southerners usually don't go past areas near Washington and Cincinnati. Unions control cities north from the previously mentioned ones. You can become their ally by being useful in their cities (you can see a flag above each city which indicates to whom this particular city belongs to). When you lower your reputation with a faction you also lower it in a given city that belongs to that faction and getting it back is a difficult task (you don't have a lot of quests, you can't make newspaper subscription etc.). It is not that hard to maintain good relations with both factions and stay neutral, however, if you want to do that you must obey the law. You can lose a lot of reputation if a contraband can be found in your carriages or you transport an illegal refugee. Warning - you can notice that during a conflict cities can change their owners.
When the level of your bad reputation reaches about -50 with one of the armies a wanted letter will be send after your character. Which each passing day more and more cities will receive them. This means that when you enter a city someone can recognize you and you will be imprisoned. This also means that bandits can also hunt you more frequently. After some time all will calm down. However, your reputation won't return. If your action result in sending a wanted letter after you, you will receive Jessie James achievement. When you are in a conflict with one of the factions and you want restore your reputation level you should try to complete contracts for cities that are besieged by their enemies - when you do that you also gain a small amount of reputation in both armies.