Trainers » Professor Elm's Training Method | Gameplay » Searching (Deck or Discard)
Can I use Professor Elm's Training Method if there are zero cards left in my deck?
No, you cannot search through your deck if there's nothing there to search. If there are cards in the deck you can fail to find a Pokemon because you don't know what may be in a deck, but since you do know whether there are ANY cards or not you cannot search through an empty deck.
Source: PUI Rules Team (2011-09-22)

Relevant cards

Note: All applicable cards may not be listed below.
COL1_82
EX10_89
EX15_79
HGSS1_100
TK4-Gyarados_25
TK4-Gyarados_25
WOTCE1_148