Its recorded history beganat least, so far as the Oxford English Dictionary knowsin the issue of the Lancaster Journal of Pennsylvania dated 5 August 1818: We have in Lancaster as many Taverns as you can shake a stick at. Another early example is from Davy Crocketts Tour to the North and Down East of 1835: This was a temperance house, and there was nothing to treat a friend that was worth shaking a stick at. A little later, in A Book of Vagaries by James K Paulding of 1868, this appears: The roistering barbecue fellow swore he was equal to any man you could shake a stick at.
The modern use of the phrase always exists as part of the extended and fixed phrase more ... than you can shake a stick at, meaning an abundance, plenty. The phrase without the more than element is rather older, but not by much.
Shaking a stick at somebody, of course, is a threatening gesture, or at least one of defiance. So to say that you have shaken a stick at somebody is to suggest that person is an opponent, perhaps a worthy one. The sense in the second and third quotations above seem to fit this idea: nothing worth shaking a stick at means nothing of value; equal to any man you could shake a stick at means that the speaker is equal to any man of consequence.
Where it comes from can only be conjecture. One possibility that has been put forward is that it derives from the counting of farm animals, which one might do by pointing ones stick at each in turn. So having more than one can shake ones stick at, or tally, would imply a great number. This doesnt fit the early examples, though, which dont have any idea of counting about them. Another idea is that it comes from battle, in which one might shake a stick at ones vanquished enemy. This could possibly have led into the early usages.
Following publication of this piece in the World Wide Words newsletter, Suzan Hendren and Sherwin Cogan suggested that it might have come from the Native American practice of counting coup, in which merit was gained by touching a vanquished enemy in battle. In that case, too many to shake a stick at might indicate a surplus of fallen enemies, and not worth shaking a stick at would equate a person with an enemy who is so cowardly or worthless that there is no merit to be gained from counting coup on him, as Sherwin Cogan put it. An intriguing idea, but theres no evidence that I know of.