When I am told to shuffle the encounter deck, does that mean the discard pile with the remainder of the encounter deck? Thank you.

They are shuffled separately. From the FAQ:

(1.21) Search Effects
Whenever a player searches through a deck, that player shuffles the deck after searching it unless a card effect says otherwise. Players do not shuffle or change the order of a discard pile after searching it.