Tail Cave is found to the southeast of Mabe Village on Koholint Island. In order to enter, Link must first acquire the Tail Key, which is hidden in the Mysterious Woods. He has to enter the woods and locate the Sleepy Toadstool, then take it to Syrup who lives in 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, 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 to Tail Cave, where he can unlock the entrance by using the Tail Key on one of the statues.