Tail Cave is found to the southeast of Mabe Village on Koholint Island. In order to enter the cave, Link must first acquire the Tail Key, which is hidden in the Mysterious Woods. To get the Key, he has to enter the woods and locate the Sleepy Toadstool, then take it to Syrup, who lives in the Witch's Hut. She will turn the mushroom into Magic Powder for him.
Elsewhere in the woods, Link will encounter a raccoon who condemns Link to become lost. If Link attempts to move north, he will simply experience the same scene over and over, much like the Lost Woods or Lost Hills of the original Legend of Zelda. Instead of doing this, he should sprinkle the Magic Powder on the raccoon, who will then regain his human form and leave Link free to continue his travels. Link can then move north and open the Treasure Chest containing the Tail Key.
Key in hand, Link can then exit the woods and travel back through Mabe Village, moving south as though heading toward Toronbo Shores. On the path, he will find a sign that directs him south to Toronbo or east to the village outskirts; heading east at this sign will bring him to the entrance of the Tail Cave, where he can then unlock the entrance by using the Tail Key on one of the statues.