Medli will give you your first bottle before entering the Dragon Roost Cavern.

After defeating Dragon Roost Cavern, go to section E6 and find a submarine. Defeat all the monsters inside to claim your prize.

When you get a letter from Beedle about a sale, go to section C2. Look for his ship. He will sell you a bottle for 500 rupees. You can also buy a heart piece and map there.

Go to Windfall Island at night. Talk to the girl next to Zunari's shop. She will tell you to go away. Do so and she will start to run. Follow her at a safe distance. When she stops, find somewhere to hide. At the end of her run, she will try to open a chest. Creep up on her. If done correctly, she will ask you some questions. Answer them all with the first choice.