When you use a Trainer that requires you to shuffle your hand into your deck does that Trainer get shuffled back into the Deck too or does it go to the Discard Pile?
No, the trainer that you play doesn't go back into your deck. {When you played it, you put it down on the table. It is no longer in your hand]
Source: WotC Chat (2001-03-29)