Although, I've been unable to find a thorough reference, the complete saying, in the U.S., at least is "nuttier than a fruitcake"... and seems to have originated about 1920. The term "nut" has been slang for deranged or off center mentally for about the same time...
Seaeching has brough up two similar clues as to when the phrase came into use
Fruitcake is also used, especially in the United Kingdom, as insulting slang for a 'crazy person' (e.g. "he's a complete fruitcake"). It dervies from the expression "nutty as a fruitcake", which was first recorded in 1935.
Fruitcake is also used as an insult directed at individuals. The use of the adjective "nutty" to mean "insane" was first recorded in 1821. The expression "nutty as a fruitcake" was first recorded in 1935.