Rashi writes: "Could it be that the Egyptians fed them fish for free? Why, they wouldn't even permit them to have bricks (for labor). If they wouldn't give them bricks, would they even consider giving them free fish? What then does (the posuk) mean by 'free'? Free from mitzvos." The words of Rashi require much in the way of clarification.

     The Sefer Pardes Yosef quotes the words of  the Biala Rebbe, R' Dov Berish zt"l: Before  Bnei Yisroel received the Torah on Har Sinai, they  were forbidden from eating fish. The reason for  this being that Hashem only permitted human consumption of animals after the מבול - flood, in  the times of Noach, since it was Noach and his sons who physically saved the animals from extinction. As a reward for their efforts, Hashem permitted humans to now eat meat from these very same animals. However, fish were never included in the animals that were saved at the hands of  Noach and his sons, and as a result, they were  never permitted to be eaten. At Sinai, though, when Hashem threatened to turn the entire world  into nothingness (תהו ובהו) and only through Klal  Yisroel's acceptance of the Torah was the world saved, now all forms of animals, fish and foul became accessible and permitted to be eaten.

     Later, however, as the sinners from among the Jewish People began complaining about their lack of food, they recalled what they ate in Egypt. "זכרנו את הדגה אשר נאכל במצרים חנם" - "We  remember the fish that we ate in Egypt freely" - in other words, they ate fish in Egypt even though it  was forbidden and they were not supposed to, because they thought they were "free" - free from following the express prohibition of Hashem.