This alludes to the pickling liquid made from brines and vinegar which is used to preserve food, and presumably to the imagined difficult of being stuck in such. The phrase was known in Dutch by 1561 - ' in de pekel zitten' meaning 'to be in a pickle'.
There are a few references to ill pickles and this pickle etc. in print in the late 16th century, but Shakespeare appears to be the first to use in a pickle, in The Tempest, 1611:
ALONSO:
And Trinculo is reeling ripe: where should they
Find this grand liquor that hath gilded 'em?
How camest thou in this pickle?
TRINCULO:
I have been in such a pickle since I
saw you last that, I fear me, will never out of
my bones: I shall not fear fly-blowing.