Bottle Locations
Bottle 1
Location: Dragon Island
Items Needed: None
You get this bottle automatically from Melody when you help her into the shrine. You can't progress in the game without it.
Bottle 2
Location: Bomb Island
Items Needed: None
This bottle is in an Enemy submarine near Bomb island. Get onto the island and you should find a guy in white with a telescope, going "Whoah!" at whatever he's looking at. Use the telescope, and he should be looking at a submarine with 1 raft attached to it. Go inside the submarine, pick off the enemies, and a chest should appear with the 2nd bottle inside.
Bottle 3
Location: Rock Ledge Island
Items Needed: 500 rupees (so rupee bag upgrade from A3 or G2)
Sometime after you get the bombs, Terry will be sending you a RED Terry Map (advertising his new bomb stock), detailing all the places he will be appearing in. On the RED map, there should be 1 face that is Terry's, but with a helmet on. There, he'll be selling a bottle (500 rupees), a heart piece (950 rupees) and a treasure map (900 rupees).
Bottle 4
Location: Taura Island
Items Needed: None
Get this from the blond girl who was held captive at Monster Island along with your sister and a brunette (obviously, this cannot be done until after you've rescued your sister). By day, she will be working near the Eskimo's store; by night, she will be snooping around near the auction house. Talk to her, and she will order you to go away. Do so, and she will sneak off. After that it's a game of stealth.
Follow her around Taura, careful to keep out of her sight (she turns around every now and then to check), until you find her trying to crank the safe in the Eskimo's store. Catch her in the act, and she will tell you her sob story and ask you to let her go. Refuse, tell her it's wrong, and she will then see the light and thank you. She will give you the 4th bottle if you get this sequence right. If not, you can always redo the quest by going in and out of a building; she should be there every time if you haven't gotten the bottle.