Orlando Neves aventa a seguinte explicação no seu Dicionário das Origens da Frases Feitas (Lello & Irmão Editores. Porto, 1992):

«Uma das tradições mais arreigadas nos pescadores portugueses diz respeito à faina dos bacalhoeiros nos mares da Terra Nova ou Gronelândia. Além dos êxitos e aventuras desse tipo de pesca, muitas tragédias ocorreram, muitos homens morreram, muitas cargas e barcos ficaram nestas águas para sempre.

Se o sentido da frase é qualquer coisa [como] "se perder", "ficar sem efeito", "não chegar a bom termo", "se frustar", parece razoável supor-se a sua origem na actividade piscatória dos bacalhoeiros.»

Acrescente-se que, além do sentido de «ficar sem efeito», «dar em nada» – que talvez possamos associar à inutilidade da água em que se demolhou o bacalhau – há situações em que a expressão tem outros significados:

1 – acalmar,serenar:

«Chegamos à esquadra e sentaram-nos num lado e ao outro grupo do lado contrário da sala e começaram a tirar-nos as identificações e mais não sei o quê! Tudo isto corria na paz dos anjos, quando surge um idiota dum chui a dizer que seríamos acusados como grupo agressor, o que fez com que se desencadeasse um pequeno motim na esquadra, só posto em águas de bacalhau, quando quatro agentes se puseram a servir de muro de Berlim entre nós e os otários.»
In http://blogadelas.blogs.sapo.pt/arquivo/2004_04.html

2 – ver-se em maus lençóis, em dificuldades:

«Sim, eu sei que não será culpa sua, mas, se você desembarcar em Lisboa sem um bom domínio do idioma, poderá ver-se de repente em terríveis águas de bacalhau.»
In http://www.filologia.org.br/vicnlf/anais/caderno02-02.html