Bottom note box.
The origins of this idiom.
The meaning of this phrase.
Phrases and Idioms - The Meanings and History For Popular Idioms and Phrases | Use this handy list of phrases to search for more!
Someone who isn't witty or sharp, but rather, they are ignorant, unintelligent, or senseless.
The structure placed in a person's backyard to store belongings in (like tools) is called a shed. Just how old are these simple constructions? Finding the answer to that question would be most useful, because the phrase would obviously have to originate afterwards. However, it is not currently known when sheds started to be built for the purpose of storing things.

A bit of history on the word, according to Online Etymology Dictionary, shows that the word shed used to be spelt as shadde as far back as the 15th century, and shadde may possibly be a dialect varient of the word shade. So that's something.

Now, even though the word shed goes back to at least the 15th century, this phrase appears several centuries later and is actually very recent by the looks of it. For example, the oldest written recording of this idiom that I could find was from July 1994, in the Colorado Springs Gazette Telegraph, where it reads:

"Critics said that Cliburn was an intuitive artist, and that once his intuition was exhausted, he had little
else to say about a piece — which was a fancy way of saying that Cliburn wasn't the sharpest tool in
the shed."

Reference: Shadde Etymology
* I knew my friend Jake wasn't the sharpest tool in the shed after I asked him to bring me a wrench and instead he brought a pair of pliers.

* The orange cat I have is not the sharpest tool among his feline companions, but his personality is certainly the best of the bunch.
Note: The origins for most common idioms cannot be said with a certainty. What's provided are theories that may be plausible to how a phrase originated, but not necessarily so.

In addition, quotes that contain a phrase may be taken from old newspapers, poems, or books that were written centuries ago, but this by no means shows they originated from these. In all likelihood, if an expression is being used in a newspaper, it's probably already well known, and thus, from an older period of time.
Know Your Phrase - The Meanings and Origins For Phrases and Common Idioms > N-Letter Sayings