I think that it's called "cold deck" because the trick is to replace the playing deck with another one, that was perviously "prepared" into some specific permutation.
Exactly. The term comes from the way you spot the switch -- cards that have been being handled a lot warm up in the players' hands. If you touch the deck and it feels cool (i.e., it is room temperature), that means it just got introduced to play.
Or it's warm because somebody just took it out of his pocket ;)
Interesting. We use the terms cooler and cold deck for an unlucky situation all the time without thinking of where they came from.