For new players who need to deal with succession crises (e.g. huge vassal revolt risk, vassals declaring war one by one) or anybody who could use some help in getting this stuff in order. I worked out this methodology in a game played as a large kingdom (not empire, not multiple kingdoms but comparable in size to a small empire by end game).
1. When your king is replaced by his successor, you don't want to unpause, even for a second, no matter what you were doing (unless in the rare case you are marrying or betrothing your heir because this can actually make AI turn down the proposal even though it said that "yes" was the expected response).
2. While paused, check out the vassal revolt risk icon at the top of your screen (the clenched golden fist), see which vassals are likely to cause trouble. At this point don't panic, a lot of the high percentage may be due to obvious factors that you will be correcting in a short while––in fact before you unpause. Actually, few of these vassals will remain a risk when you're unpausing if you follow the steps below.
3. The above-mentioned most important and obvious factors are your demesne limit (top right corner of your screen; this is the number of counties or baronies you hold personally) and the number of ducal titles you hold if you're a king or emperor (this can't be above 2 or you face opinion penalties; just click the face of your character and you'll get his character sheet, on which you can see the list of his titles).
4. Check out your advisors (crown icon in the top left), make sure your Steward and Chancellor are people with the highest stats available. But don't fire a powerful vassal if he's already your Councillor and isn't really bad! Fired councillors have a negative opinion modifier (they dislike you for firing them), so hold on for a while, you can replace them when the times are calmer. Having a good chancellor and a good diplomacy stat on your ruler and his wife helps. Chancellor helps diplomacy, i.e. people's opinions of you, Steward helps your demesne limit.
5. Before you give anybody any land, you first need to plan give away the excess duchies and the demesne holdings, if you have any. The excess holdings hurt your income anyway, so it's no use clinging to them. But don't give them away to just about anybody and don't make a random decision about which titles (counties, baronies) you want to give away. We will be dealing with the demesne give-away in a separate mini-guide below. You will need to keep some structure. First of all, basically make a (mental or paper) list of which vassal desires which barony, county or duchy and how bad his opinion of you is. You don't want to be giving them more than necessary. Sometimes just going down to two duchies (if you're a king) and to your demesne limit (for counties and baronies) and using honorary titles and/or cash gifts may be enough.
6. Here's the miniguide to giving away titles (this may seem complicated but don't be scared!):
(i) first of all, if you have the "wrong holding type" problem (icon representing a gate with bars), give those holdings away first (this is typically cities and bishoprics if you are a castle vassal, i.e. normal feudal noble) because they don't give you normal income, even if you aren't above your demesne limit;
(ii) if you are a king or emperor, you want to give duchies out first (until you have only 2) before giving actual land (baronies or counties) away if you don't have any counties in the respective duchy or if you're prepared to part with the county or counties that you do have there; this is because you need to go down to 2 duchies as a king anyway;
(iii) normally you want to give away baronies before you start giving counties because baronies provide income from only themselves, while counties are essentially baronies ("capital baronies", "county seats") that collect some taxes from the other baronies (typically the bishopric and the city but some counties have several baronies while some have only one, the capital);
(iv) if you have a vassal who desires the specific holding that you hold (which gives you a negative opinion bonus for each such holding, typically -25), give it to him; you will not only lose that negative modifier but also gain a positive one for granting him a barony, county or duchy (increasing with the rank of the title) -- you normally don't need to give them all the titles they desire, one should be enough;
(v) check out which counties or baronies are more valuable (you want to keep them), i.e. better upgraded or better located strategically or bring you more cash: for a county this typically relates to the number of baronies that exists under it (and counties with cities that have ports are likely to be richer), for a duchy to the number of counties under it but also check how many baronies those counties have, but also check out tax income and levy size on the province information tab;
(vi) don't appease counts if you're going to give the respective whole duchy (to which they belong) away, don't appease barons if you're going to give the whole county (to which they belong) away (if you ever actually want to appease barons at all, which is rare unless you're small; barons don't rebel against powerful kings even if the revolt risk if 80% or something); their new liege will be your vassal instead and will have to deal with their loyalty, not you;
(vii) don't give land to people with the ambitious trait unless you give them a lot of titles in one go and have a very good reason to give them that land (the penalty to opinion for ambitious is -50, which is very big, but if you give a duchy to a courtier for +140 to opinion, this is not overwhelming), and when you have the option, prefer people with high stewardship (they will earn more and thus pay more taxes);
(viii) don't really try to appease people who have the ambitious trait or who hate you beyond any help unless you're ready to shower them with gifts, or else they will just have more power (including levies they can call and land you need to siege before they give up) when they do rebel and they most likely will rebel if they're at 10% risk or above, let alone >30%;
(ix) remember that people with >10% revolt risk will actually rebel sooner or later before their rebellion risk gets down to 0%, so if you know you won't be able to appease someone, don't invest land or cash you need;
(x) if you are at or below your demesne limit, giving honorary titles (the boost is small, -10 for most titles and -15 for the better ones) should take priority before giving land;
(xi) giving cash (the Send Gift diplomatic option) is still preferable rather than giving land in many circumstances, depending on the power of the character (if you can appease a duke with a 20 gold gift, it's better than giving him any land but some powerful vassals would require >400 gold for a gift and that's normally not preferable, you'd normally prefer to give a barony or county in such a case);
(xii) if a potentially troublesome vassal would make a good councillor (isn't much worse than the best available candidate) or you desperately need that vassal's revolt risk to be eliminated, you can appoint him to the council; this is better than giving him valuable land;
(xiii) remember to interrupt your donation spree if your intended recipients are already appeased (or would likely become appeased by an honorary title or comfortably small cash gift, depending on your economic power); remember that for each duchy or county or holding above the limit that you dispose of, all your vassals will hate you less (effectively improving their opinion of you by 10 per each such title until you're down to your limit);
(xiv) if all you need is just to dispose of the surplus titles to get back down to your demesne limit then give everything to your heir, for example because your vassals don't want (m)any specific titles and/or they hate you only moderately, i.e. the negative opinion isn't all that horrible, then you will normally prefer to give the surplus demesne land to your heir (unless your heir is unmarried/not betrothed to a suitable candidate yet, so you need to keep him in your court to control him, but betrothing that kid to an available rich heiress (female ruler, young enough) and giving him land when he's already betrothed will generally make sure he keeps his fiancée and marry her when the time comes, it's only that you won't be able to change to a "better" one if a "better" one comes up, or choose the new one if the old one dies; but with betrothal or marriage you need to be careful with unpausing the game);
(xv) I would almost forget, but don't try to appease people who are weaker than their title would suggest, e.g. dukes of 1 county (and 1 vassal or none) aren't more powerful than counts having 2-3 counties and those big counts are more dangerous than the small dukes and should get priority. Unless you have a good reason to be appeasing them (e.g. they have a duchy that has two counties under it, of which they have 1 and you have 1, so give it to them if you're above the demesne limit, this may be worth it);
(xvi) Try not to butcher up your demesne. Avoid having counties in the duchies that belong to your duke vassals, or baronies that belong to your vassal counts unless they're safe and won't rebel. Try to preserve the structure of de iure duchies if you do need to give counties away. For example, if you're the King and you have Duchies A, B, C and D, you're better off giving full duchies A and B (and keeping full C and D) rather than a half of each. (This was a simplification that can be disproved if we get into detail. Just don't get into situations where your new duke will desire your counties.)
7. Short recap of appeasing is as follows: you need to give excess duchies and excess or wrong type holdings anyway, so do that; you don't want to give more necessary, you want to give honorary titles rather than cash and cash rather than land; and if you only really need to get down to your demesne limit so that your vassals start to like you (e.g. because you were at full demesne limit when your king died but your heir was a duke and had several holdings, so you're above the limit now but otherwise they don't hate you), then you prefer to give all the surplus land to your heir (he will have his own reservoir when he succeeds in turn, and he will be getting prestige from all the holdings), provided that you've already chosen his wife. And if you aren't favouring your dynasty members, you want vassals with high stewardship, especially if they will have their own vassals under them. And you want to give a council seat to your vassals if they are actually qualified (before you give them land or cash). And you don't want to give anything to people who are guaranteed to rebel (or to close relatives of such people) or ambitious people.
8. Check the vassal revolt risk (golden fist) icon again. See the troublemakers. Here's the procedure for the remaining troublemakers:
(i) If they are powerful and especially at 10% or below, you want to give them an honorary title if you haven't yet.
(ii) If they already have honorary titles but haven't been given gifts yet and the cost of the gifts isn't prohibitive, then give them gifts (this tends to be cheaper than war anyway but not always).
(iii) If they still have not been pacified, see if you can appoint them to the council for any slot where you don't particularly mind them being (a replaced courtier won't rebel).
(iv) For any troublemakers that still remain, choose the one to appease with your chancellor's diplomatic efforts (usually a combination of how high his revolt risk is and how powerful he is), the chancellor produces a +25 opinion boost when successful, and he can actually produce that bonus with himself if he happens to be that rebelling vassal you want to appease! (I've actually done this successfully.);
(v) Also, one more thing, actually: if you ask a vassal to educate a child (Educate Child diplomatic option) from your court, you will get a whole +20 opinion from that vassal (this stacks for two children, I think). This is really powerful but you need to make sure the vassal is a capable guardian (good traits, good Learning stat, good other stats, appropriate culture).
9. This may not be immediately obvious but opinion bonuses are personal, which means they are more useful on more powerful vassals. For example, one duke who holds a whole six duchies, will be appeased by honorary titles, council appointment and Educate Child (or even land donation) equally as well as a duke with 1 duchy. He will only be more expensive to Send a Gift to. If you have the big vassals on your side, then you may actually not need to appease small vassals that just happen to be ambitious malcontents with poor stats or otherwise incompentent/dangerous people.
10. Put your court chaplain in Rome to work on religious relationship with the Pope. You don't want to get excommunicated. Getting excommunicated means a lot of trouble because everybody has a Casus Belli against you and can declare war on you freely (perhaps existing truce will prevent this). If the Pope has a really bad opinion of you, I'd put your chancellor at Rome too, for a tandem.
11. Remember to pay proportionally more attention to more powerful vassals and especially keep the most powerful vassals (e.g. dukes of several duchies or even kings if you're the emperor) on your side and with a good enough opinion. His levies can help you crush the smaller vassals when they rebel (and the better his opinion of you, the more levies you will get).
12. Don't have Feudal Taxes or Feudal Levies or Royal Authority any higher than you really need (or want) if successions are problematic. Or reduce them with old rulers, wait 10 years after succession to get them back.
13. Any vassals that rebel will be treated as traitors. This allows you to take one of their titles away without any bad reactions from other vassals (but you still get negative reactions if you exceed your demesne limit or get too many duchies as a king/emperor!) and reassign it. You can keep it in your demesne (if you don't exceed the limit) or give it to somebody else. Or if you have one barony in your demesne, you can give that barony away and keep the county you've just taken from a traitor. Nobody will rebel while you're paused, so you're safe if you pause immediately. If you confiscate a ducal title, remember not to have more than 2 if your vassals are still likely to rebel.
14. If your rebelling vassal becomes attacked by someone else (e.g. holy war by a Muslim ruler or normal war by a claimant), you should probably offer white peace as soon as you're able, in order to avoid your vassal concluding peace with the new attacker and ceding land or becoming his vassal. You may want to take white peace if you have several rebels. Prolonged civil war isn't good for you. Sieges take long and your soldiers die. You can try to arrest that rebellious vassal later (he will only go to your prison if he surrenders to you; also, you will get +50 prestige bonus only when he surrenders, but when he white-peaces, then he loses 100 prestige but you gain 0).
This sounds complicated, I know. But just print this sheet and go through one succession, you will get the gist of it. Also, if you send me a save game from the moment your old ruler has just died, I can go through that save and tell you exactly what I did (i.e. which title to whom, how much gold etc.).
Please let me know if I'm wrong anywhere or if you think important details are missing or something is redundant. If needed, I will make a PDF version.
EDIT: Azaz's post below made me recall one other thing I wanted to mention but I thought it might be too advanced. Basically, sometimes dukes desire the control of a county (or counts the control of a barony) that somebody else holds directly of you. For example, if you're the King of Poland (England) and have a Duke of Silesia (Lancaster) and a Count of Cieszyn (Earl of Lancaster) as your vassals, the Duke of Silesia will want control of the Count of Cieszyn. This is similar to giving a county away, except when you give a way a vassal, you don't lose as much (in taxes or levies) as when you give away a county from your demesne.
Also, if you're unsure whether simply getting rid of excess land (above your demesne limit) will be enough to make vassals stop being angry, you can make counts (barons if you have any baronies) first until you are down to the limit. If the big vassals still don't like you, transfer the vassalage of those smaller, new vassals, to the bigger ones.
For example, as that King of Poland, if you have Cieszyn (County) in your demesne and are one county above the demesne limit and the Duke of Silesia desires it and is likely to rebel, you can create a count of Cieszyn. The Duke of Silesia will like you slightly better because you now don't have an oversized demesne. But if he's still likely to rebel, you can transfer to him the vassalage of the new Count of Cieszyn. Then the Count of Cieszyn will become the vassal of the Duke of Silesia, who remains your vassal. The county doesn't leave your kingdom, there's only a middleman now.
Also, in some situations giving a holding away to someone else stops people from liking you less because they desire it. They dislike the new holder instead.
And if you, say, have a duchy that has 3 counts in it, and each count desires a duchy, and you give the duchy to one of them, you don't have to worry about the other two. They will become his vassals (most likely), and he will have to deal with them.
Edit (thanks to Paul Drye): Releasing a prisoner grants you a minor opinion boost with every vassal (+10 for being merciful). This does not stack.
Edit (thanks to Bylandt): If you need a place-holder, you can grant a title to a very old courtier who has a wife past child-bearing age (if she's 45 and he's 85, this is better than if she's 75 because she won't likely die sooner than he dies, in which case he could remarry and actually still have a son--I once made an 84 year old bachelor a duke and he still started a dynasty there).
Edit: Sometimes your ruler or his heir is married to a female vassal, holding land. You can give land to that female as a place-holder, although sometimes she may have a different succession law (e.g. gavelkind, so the titles will be split among the sons) or elective (strange things can happen). This is the safest with primogeniture. If her heir is your heir or your heir's heir (by which I mean heir apparent, eldest son, not a temporary heir presumptive like a brother or cousin), then the inheritance will eventually be joined. Rarely, but sometimes it actually can be useful (normally there's a male to give a title to).