The text I've seen for this card (I don't have a physical copy yet) is
"Response: After you win a challenge in which The Golden Company participated as an attacker, return 1 random card from your discard pile to your hand"
Given that the order of cards in your discard pile can matter for several effects, I feel that if this wanted you to shuffle your discard pile it would say so. As we haven't required a die or other random-number generator before… I'm a little surprised by this wording.
Is there a precedent for picking a random card from a visible play area? I wonder if there are any similar cases from the CCG that serve as a guide…