As I recall, which is admittedly vague since I haven't had it happen in a while....
1. Your characters imprisoned by other countries - You send a diplomat, negotiate, pay some $$ and get him back. This is very rare for me as most such imprisoned characters were sent on death missions to get rid of them. Rarely I have had a good general get captured though...Also, you have to remember what country has the character cause there is no way to see who is being held from your menu's
2. AI Characters that you have imprisoned - The AI has to enter negotiations to release the prisoner. This is pretty rare. I had it happen before the latest patch, maybe 2-3 times during a long game, but not since. Don't know if it was broken in the latest patch. So basically you get a pop-up diplomacy dialog with an accept/decline offer. I think the individual in question needs to have decent stats AND decent loyalty for the AI to consider it.