Look at /bmap. See which areas have prisoners. It helps if you know which beastmen were attacking in the Besieged when she was kidnapped, but if not, you'll just have to try all three.
Find a place with prisoners. Obviously, there's no point in looking at a place with no prisoners. Get a respective key drop (or, much easier if you have this option, a high level THF with lockpicking tools). Note that there are three types of keys for each of the beastmen, and only one of them is for prison cells.
Poke around in the various cell locations (see wiki) until you find the NPC you're looking for. Deal with any nearby beastmen somehow (wait until they turn away, kill them, sleep them, whatever). Pop cell door. GTFO. If you have found all of the prisoners in a location (see /bmap for total number) and none are the one you want, you might as well rescue one of the ones you did find, before you go. (If you go with the THF option, just rescue anyone you come across, period.)