Nowadays, as mainly city-dwellers, we think of the needle in the saying as if it were a relatively tiny thing for sewing buttons on or whatever. However, the name 'needle' was also given in farming circles to a large wooden or metal peg that was driven into a haystack to hold the sheaves together. Thus, there actually were "needles in haystacks" and they were rather more easily found than we imagine!
I should perhaps have pointed out above that the idiom is very old and originally had forms as 'looking for a needle in a bottle of hay' and 'looking for a needle in a meadow'. These instances may very well have been in reference to actual small needles as we now think of them.
Whichever...the saying invariably suggests something that is almost impossible to find.