Bigger Deku Seed Bag: Hyrule Market
Go to the Shooting Gallery in Hyrule Market and play. It costs 20 rupees to play, but if you miss one or two targets, he'll give you a free try. Get all the targets and he'll give you a bag that can hold a maximum of 50 Deku Seeds. After you win the Deku Seed bag, if you play again and get all the targets, you get a purple rupee.

Deku Sticks: Lost Woods
Enter the Lost Woods from Kokiri Forest and take a right, then go through the other tunnel in that room. Towards the back of the area is a Business Scrub who will sell you an Deku Stick upgrade for 40 rupees. With this, Link can hold a maximum of 20 Deku Sticks.

More Deku Sticks: Lost Woods
Enter the Lost Woods from Kokiri Forest and take the following tunnels: right, left, right, left, left. You should be in the area with the two Business Scrubs. Walk in the tall grass near the butterflies and you should fall into a grotto. In the grotto is a little stage. Put on the Skull Mask and step forward. Little Dekus will jump up and gather around you and dance. Then they'll dance over to a bigger Deku. He will give you a Deku Stick upgrade. Now Link can hold a maximum of 30 Deku Sticks.

Bomb Bag: Dodongo's Cavern
You can find the Bomb Bag in Dodongo's Cavern. Please refer to the walkthrough for more information.

Big Bomb Bag: Hyrule Market
After you defeat Dodongo's Cavern, go to Hyrule Market, to the Bombchu Bowling Alley. The Big Bomb Bag is one of the prizes you can win. With the Big Bomb Bag, Link can hold a maximum of 30 bombs.

Biggest Bomb Bag: Goron City
On the turquois level, there's a big Goron rolling around the level. Find his sign and stop his rolling with a bomb. He will give you the Biggest Bomb Bag. With this, Link can carry a maximum of 40 bombs.

Adult's Wallet:
After you have gathered at least 10 Gold Skulltula tokens, go to House of Skulltula in Kakariko Village. Talk to the dude in the right corner closest to the door, and he will give you an Adult's Wallet. With this, Link can hold a maximum of 200 rupees.