Carry More Deku Nuts #1: Go Right, Left, Right, Left, Center, and then Left in the Lost Woods and bomb the rock there. Fall down and beat one of the Deku Scrubs and pay him 40 rupees to carry 30 Deku Nuts.

Carry More Deku Nuts #2: Get a Mask of Truth from the Happy Mask Shop.

Go to the Lost Woods and turn Right, then Left, Right, Left, and Left again. Go to the back of this area (near some butterflies) and walk around until you fall into a hole. Inside, wear the Mask of Truth and the Deku Scrubs there will hate you. From there, go onto a little ledge where a small tree is. The small tree will turn out to be a Deku Scrub, which will marvel at your mask and then allow you to carry 40 Deku Nuts. (A weird bug in the game keeps you from doing this after ever becoming Adult Link, so do it as soon as you can!)

Carry More Deku Seeds #1 (Young Link): Go to the Lost Woods and turn right once. Shoot the target thing hanging off a tree and get 100 Points three times, and a Deku Scrub will give you the ability to carry 40 Deku Seeds.

Carry More Deku Seeds #2 (Young Link): Go to the Shooting Gallery in the Market. Hit all the targets to win the ability to carry 50 Seeds.

Carry More Deku Sticks #1 (Young Link, although it may be possible as Adult Link too): Go to the Lost Woods. Go left, and then left again, and then climb down the ladder. Walk across the room (there will be a gossip stone nearby) and reflect the Deku Scrubs nuts. He will then sell you the ability to carry 20 Deku Sticks for 40 Rupees.

Carry More Deku Sticks #2 (Young Link): Get a Skull Mask from the Happy Mask Shop.

Go to the Lost Woods and turn Right, then Left, Right, Left, and Left again. Go to the back of this area (near some butterflies) and walk around until you fall into a hole. Inside, wear the Skull Mask and the Deku Scrubs there will go nuts. From there, go onto a little ledge where a small tree is. The small tree will turn out to be a Deku Scrub, which will marvel at your mask and then allow you to carry 30 Deku Sticks.

Carry More Bombs #1 (Young Link): In Goron City there is a giant Goron that is rolling around on the third floor. Toss a bomb at him near the sign that says 'I will reward you if you stop my wild rolling'. He will give you a bag allowing you to carry more Bombs.

Carry More Arrows #1 (Adult Link): Shoot all the rupees in the Kakariko Village shooting gallery to gain the ability to hold 40 arrows.

Carry More Arrows #2 (Adult Link): Get 1500 points at the Horseback Archery challenge in the Gerudo Fortress (after winning a Piece of Heart for 1000 pts.) to get a 50-arrow quiver.