How should I punish my revolting vassals?

You have two major options here, and one is much easier than the other:

  1. Take a title, release him, let him rebel, imprison him, rinse, repeat. Eventually, you've taken so many titles that he isn't a Super-Duke anymore, and when you finally take his last title, he won't even be a noble anymore. This may take a very long time; probably so long that your Duke dies of old age and you start dealing with his heir instead.
  2. Who said you have to release him? Just let him rot. He can't raise a rebellion if he's in your dungeons. If his problem with you is personal, not political, then stick him in the oubliette so he'll die sooner, and you can deal with his heir instead. (If his major penalties to opinion are things like "Ambitious" or "Greedy vs. Honest", then its' a personal problem and his heir will probably be different – though you should examine the heir to be certain. On the other hand, opinion penalties like "Too many duchies" and "Desires that shiny county you've got" will be inherited by his heir.)

As a side note, if you assign your Spymaster to seek out plots in an unhappy noble's capitol, you'll probably find a plot against you. Then you get the option to arrest that noble, which might or might not work depending on your relative Intrigue skill. If it doesn't work, he'll rebel immediately, and then you can crush him like the bug he is and look at those above options.