Minuet of Forest — Sheik teaches it in the Sacred Forest Meadow when you first arrive as an adult. Warps to the Forest Temple entrance.
Bolero of Fire — Sheik meets you on the broken bridge in Death Mountain Crater once you cross with the Hookshot. Warps to the crater by the Fire Temple.
Serenade of Water — Sheik appears after you take the Iron Boots in the Ice Cavern. Warps to Lake Hylia.
Requiem of Spirit — Sheik teaches it the first time you leave the Spirit Temple at the Desert Colossus. Warps to the colossus and makes the desert crossing one-time only.
Nocturne of Shadow — Return to Kakariko with the Forest, Fire and Water medallions; the well bursts and Sheik teaches it after the cutscene. Warps to the Shadow Temple's entrance.
Prelude of Light — Visit the Temple of Time with the Forest Medallion and Sheik teaches it. Warps straight to the temple.