So I got the Mushroom and gave it to the witch in the Magic Shop, she told me to come back later to get something. When is "later"? I have beaten the first 3 dungeons and got the Master Sword.
Yup, what CSD said. If you just go outside, leave one screen to the left and go back into the Magic Shop, the potion will be waiting for you right next to the witch. You just grab it and it's yours.