Persuading nobles to join your Rebel faction requires high Persuasion skills, as well as that noble having a high personal opinion of you. You can do tasks for that noble to raise relations, or assist them in battle against common enemies. That gives you ONE noble as an ally.
Once your Rebel faction succeeds in taking the last remaining castle or town from the current Vaegir king, your faction will BECOME the "Vaegirs", and the "Rebels" tag will vanish. In essence, it's not YOUR kingdom, it belongs to the claimant to the throne whom you have chosen to support.
If you're not overly familiar with the game, backing a claimant is a very difficult road to take. Joining an existing faction and moving up the hierarchy to control several castles or towns is tough enough.