There are exactly thirty-six heart pieces in Hyrule. Note that for every four heart pieces you find you get an extra heart container.

Lost Woods (K) 1. Go to the right as you enter the Lost Woods. Jump on the small log and a Skull Kid will appear. Play Saria's Song and he will give you a heart piece.
(K) 2. Deeper in the Lost Woods are two Skull Kids on a tree. Talk to them and play their song game. After two successful songs (this was my number, might be different for you) they will give you a Heart Piece.

Hyrule Field (B) 3. In the big fenced off area in front of Lake Hylia set a bomb and a hole will open. Go in the hole and a Buisness Shrub will be inside. He will sell you a Heart Piece for ten rupees.
(B) 4. By the river that is next to the big wall next to the Castle Walls there is a Red Leafed tree. At the base of the Tree set off a bomb and go in. Equip the Iron Boots and Zora Tunic, or Golden Scale, and sink to the bottom. Now get your heart piece!

Lon Lon Ranch (K) 5. At the very end of the Corral there is a Tower. Go inside and push the blocks so you can get in the crawl hole. Inside is a Heart Piece.

Goron City (K) 6. At the bottom of the city is a large pot. Light all the torches there to get the pot to spin. Then go to the second floor and toss a bomb into the pot. The second time you do this a Heart Piece will pop out!

Zora's River (K) 7. Play the Song of Storms for the Frogs and they will give you a Heart Piece.
(K) 8. Play all the songs on the top row in your sub-screen for the Frogs. When they are all big they will challenge you to a game. If you win they will give you a Heart Piece.
(K) 9. Take a Cucco to fly up to the Plateau over where the Frogs are. On it is a Heart Piece.
(K) 10. Near the entrance to Zora's Domain there is a Heart Piece. Use the Boomerang or a Cucco to get it.

Zora's Domain (K) 11. Behind the waterfall is a Heart Piece in a chest. To make the chest appear go up to King Zora's chamber and get some fire on a Deku Stick. Then run around Zora's Domain and light all the torches.

Zora's Fountain (A) 12. On one of the Icebergs to the far right is a Heart Piece. Simply hop your way over there.
(A) 13. On the bottom of Zora's Fountain is a Heart Piece and a mess of Rupees. Put on your Iron Boots and Water Tunic and sink down there.

Ice Cavern (A) 14. In one of the rooms there is a Heart Piece frozen in Red Ice. Just use Blue Fire to thaw it out.

Kakariko Village (K) 15. Get a ride from the Owl on top of Death Mountain and he'll drop you on the roof of Impa's house and drop onto the balcony over the Cucco pen. Go in the crawl hole and you'll emerge next to a Cow and a Heart Piece!
(A) 16. On the roof of Granny's Potion Shop is a man. Use the Longshot to get on the roof and talk to him. He'll give you a Heart Piece.
(B) 17. Kill 50 Gold Skulltulas and go to the House of Skulltula. One of the kids will give you a Heart Piece.

Kakariko Graveyard (K/A) 18. Place a Magic Bean in the soft soil in the graveyard. Come back as an Adult and ride the stalk to the box. Smash the box and get your heart piece!
(K) 19. At night play "Dampe's Heartpounding Bonechilling Gravedigging Tour" and eventually he'll dig up a Heart Piece.
(B) 20. Pull all the gaves you can and one will have an underground tomb with a heart Piece in a chest.
(A) 21. Beat Dampe's Ghost in a race under one minute and he'll give you a Heart Piece.
(A) 22. After Dampe's Ghost gives you the Hookshot go through the door and play the Song of Time at the Blue Block. Go through the opening and you'll be in the windmill. Hop on the spinning platform and ride it to the opposite side. Jump to the ledge and pick up the Heart Piece.

Dogondo's Cavern (K/A) 23. Put the magic bean in the soft soil. Retrun as an Adult and ride the stalk to above the Cavern. Hop off and pick up your Heart Piece.

Hyrule Market (K) 24. Play the Bombchu Bowling Game. Eventually the prize will be a Heart Piece.
(K) 25. At night bring the Fat Lady's "precious" Little Richard back to her and she'll give you a Heart Piece. Richard is the whitest dog there.
(K) 26. At night use the Lens of Truth to beat the Chest game. The prize is a Heart Piece.

Death Mountain Crater (K/A) 27. Do the whole bean thing on the soft soil patch by the warp spot. Return as an Adult and ride the stalk to the large Stone. Jump on it and pick up your Heart Piece.
(A) 28. There is a large wall with indentings on it. Go around the Crater and climb down the wall to a nook. In the nook is a Heart Piece.

Lake Hylia (A) 29. Get the Golden Scale and dive in the pool in the Labratory. If you touch the bottom the Scientist will give you a Heart Piece.
(A) 30. Do the Magic Bean deal on the soft soil patch next to the Labratory.

Gerudo Valley (B) 31. In the waterfall there is a Heart Piece in a nook. Climb the ladder to get to it.
(A) 32. Use the Longshot to get to the box on the opposite side of the Valley. Smash the box with the Hammer to get the Heart Piece.

Gerudo Fortress (A) 33. Get more than a 1000 Points on the Horse Archery Game to get a Heart Piece.
(A) 34. In a large chest on the roof of the Fortress is a Heart Piece.

Desert Colossus (K/A) 35. Do the whole Magic Bean thing on the soft soil hole by the entrance to the Spirit Temple. Ride the stalk to get Heart Piece on the arch in front of the Temple.

Fishing Pond (A) 36. Catch the biggest fish in the pond and the man will give you a Heart Piece.