During your travels you will come across people who claim to be deposed from ruling a particular faction. Each claims the throne of a different faction and has his own explanation for why he is the true leader and the current king is a usurper. After you have met each claimant you can mention the claimant's name to that faction's king to hear his side of the story.
The claimants are Lady Isolla of Suno (Swadians), Prince Valdym the Bastard (Vaegirs), Dustum Khan (Khergits), Lethwin Far-Seeker (Nords), and Lord Kastor of Veluca (Rhodoks). They travel around from time to time, but they will always be in a town or castle that is not owned by the faction they claim the throne of. The Traveler who randomly spawns in taverns can tell you their current locations for 30 gold per name.
Taking up a claimant's quest to take the throne is a difficult process, but it plays completely differently from being a regular vassal. To join a claimant you will need 200 Renown. You also must not be in a faction; if you are in a faction you will have to ask the king to release you from your oath unless the claimant wishes to rebel against your faction.
When you have officially joined the claimant he will declare you the marshal of his new faction and joins your party as a companion; you can customise his skills and equipment just like your other companions, but unlike regular companions he has no likes and dislikes. If you ask him how the war is going he will give you an overview of how many fiefs and lords each of the two factions has. You can pull out of the rebellion at any time by talking to him; when you do this he will leave Calradia forever, and the rebel faction will merge back with the original faction.
After rebelling, a new faction is formed (with "Rebels" appended to the name), and all properties the rebels possess will be labelled in red. You will be permanently at war with the original faction for the duration of the rebellion; there is also a small chance that other factions will declare war with you. You can now start besieging the fiefs held by the original faction (as well as those held by any factions that declare war on the rebels), but you can also win fiefs without bloodshed by talking to the lords of the usurper's faction.
When you confront a lord of the usurper's faction you can try to convince him to join your cause. If he is attacking or fleeing from you he will refuse to discuss the matter; the best time to talk is when he is resting at a town or castle. What he says in response to the initial announcement indicates his feelings on the matter. You then get to try to convince him by giving a reason for supporting the usurper (legality, justice, inevitable victory, greed, something else, or more than one reason).
Once you have chosen an argument to use some calculations will be shown on the screen. Your Persuasion skill sets the baseline; after this the arguments you used with other lords will be taken into account (if you have used too many different arguments he may decide you are just saying what he wants to hear); your reputation with him is then taken into effect, followed by the argument you used (if you choose the reason that most closely matches his feelings on the matter you will have a better chance), and finally his trust or dislike of any vassals you have already convinced to join your cause. After these calculations are complete he will announce his decision, and tell you how persuasive your argument was. If he was not convinced, the conversation is over. You can try to convert him again after about a month. If you convinced him, however, he becomes a vassal of the rebels and is now under your control. You can direct him around using the normal functions of a marshal. When he is travelling on the map you can also talk to him to add or remove troops from his party (once the rebellion ends you will lose this ability).
Any lords you recruit will convert to the rebels along with all their fiefs. If you take fiefs by force, however, they will have no owner. The claimant will then ask you who to distribute the fiefs to; you can give them to yourself, the claimant, or any of the lords currently on your side. The fief distribution list clearly shows how many fiefs of each type each lord currently owns. In many cases, giving a lord a fief will raise his regard of you but lower that of other lords; for best results, give out properties as evenly as you can. You may like to take note of the names of recently converted fiefs so you can know what type of fief you are handing out. If you have captured a fief and later convinced the original owner to join you, be sure to give his fiefs back to him if you get the chance.
The rebellion does not end when you have captured all fiefs; you will need to track down and convince or defeat any remaining lords, as well as any caravans still belonging to the original faction. When all parties belonging to the faction have been eliminated the rebellion will end; the rebel faction will rename to the name of the original faction and takes on their allies and enemies, and the claimant will leave your party to take the throne (the usurper will leave without a trace). Any lords who did not join your cause will now join up with the reunited faction, although their opinion of you will be unaltered. You will remain the marshal of the faction until the ruler decides to call an election.