You first have to learn out where she is being held. If you look around the undergas, you'll either find her, or find some mosquibees who know where she is. I'll just give you the location in the next hint, since there's no way to be subtle.
She is located in the jail in the Building Company on the Island of the Wannies.