Kingdom Army quests
For this quest, simply follow the army. After a certain number of days the quest will be completed. If you venture too far away you will receive warning messages, and eventually you will fail the quest. Repeated failures may result in you being expelled from the faction.
Report to the Marshall
Go to the marshall and report for duty. This most commonly involves following him.
Deliver Heads [sic] of Cattle
For this quest, go to the nearest village and buy the specified number of cattle, then drive them towards the army. To drive them, "talk" to the cattle party and choose to drive them; they will then flee from you just like a smaller enemy party would. You will receive gold and EXP based on your character level.
For this quest, simply travel near each location until you are told it is scouted. When you have visited all three, return to the marshall. This mission earns you 100 EXP and a point of relations with the marshall.
Kingdom Lady quests
Rescue Lord by Replacing Him
This quest only shows up if the lady's husband has been captured. His wife has a simple plan: you are to go to the prison and change clothes with him, allowing him to leave while the guards are too drunk to spot the difference. After you swap clothes you spend a normal prison sentence there, and eventually get released. When you are free again, return to the lady for 2000 EXP and 1500 denars.
Deliver Message to Imprisoned Lord
This quest only shows up if the lady's husband has been captured. She wants you to take a message to him in the prison. This quest nets you a mere 10 denars, but you earn the respect of the imprisoned lord.
Challenge (Lord) to a Trial of Arms
A lord has insulted the lady's honour, and it is up to you to challenge him to a duel. You will spawn in the nearest town's arena, armed with all your normal equipment (including your horse if you are using one). Defeating him should be easy; afterwards he will strongly dislike you, but the lady will reward you with 1000 EXP and 2000 denars (to maximize your profits, refuse to accept the reward - you will receive it anyway and your relation with the lady will increase more). If he defeats you she gives you 400 EXP and thanks you for trying.