Hypothetical situation:

My Opponent (targ) has a Dragon Skull in shadows and a Refugee of the Plains in play. He brings dragon skull out of shadows and I cancel the response. Does he have to put the dragon skull on his character or does it get discarded?

Straight out of the FAQ:

"If the Shadow card cannot legally attach (or the attempt to attach is canceled) the card is instead discarded and is not considered to have come into play."