Do I take random Villain Deck Cards
from the Discard pile and shuffle them back?
yep, that s the way i do it.
If you haven't already seen it, this should help quite a bit:
Unofficial FAQ (Answers are from the designer though)