Upgrade 1: 40 Bullets The first upgrade for the bullet bag can be gotten in the Lost Woods. Enter, and make a left hand turn in the Lost Woods, and you should come to a tree with a metal circle hanging from it. Equip your slingshot, and fire into the center of the circle 3 times, scoring a 100 three times. Then an amazed deku scrub will come out and give you this upgrade.
Upgrade 2: 50 Bullets This upgrade can be obtained in Hyrule Castle Town. As a child, go to the shooting range right next to the entrance to the Castle Courtyard. Play the game and, using good timing, destroy the 10 targets, to get the upgrade.
Deku Stick Upgrades
Upgrade 1: 20 Sticks-This upgrade can be gotten as child Link in Lost Woods. To get it, enter lost woods and make two lefts in a row. Then jump down past the magic bean soft soil area and go all the way to the end. Defeat the business scrub you see and purchase the upgrade from him for 40 rupees.
Bomb Bag Upgrades
Upgrade 1: 30 Bombs To get this upgrade, go to Goron City. Find the giant rolling goron on Medigoron's floor level. Using your bomb, stop him in front of the sign in the short temple. He will then give you your upgrade, enabling you to carry 10 more bombs than before.
Upgrade 2: 40 Bombs To get this upgrade, go to Hyrule Castle Town as a child. Go to the bombachu bowling alley (next to the stairs and the beggar). Enter the game, and win the prize. The prize may be anything though, so you may have to play a few times before the prize becomes the bomb bag.
Deku Nut Upgrades
Upgrade 1: 30 Deku Nuts This upgrade can be gotten most easily as an adult in Zora's River. You must have planted a magic bean near the entrance as a child. Climb on the magic bean plant until it hovers you over the high area with a rock surrounded by tiny rocks. Jump off, and bomb the rock, exposing a hole. Go in, and defeat the Deku Scrub at the right. He will offer you the chance to carry 30 deku nuts. Pay 40 rupees to get the upgrade.
Quiver Upgrades
Upgrade 1: 40 Arrows This upgrade can be obtained in Kakariko Village as an Adult. Go to the shooting range (the red brick building near the Cucco Lady's house). Play the game for 20 rupees. It may take a few tries to get, but once you win, you'll get the upgrade, and then be able to carry 10 more arrows than before.
Upgrade 2: 50 Arrows This upgrade can be gotten as Adult Link, after you have obtained the Gerudo Membership Card. Since you have the Membership Card, enter Gerudo Valley, and go up the path past Gerudo Training Ground. Talk to the lady there, and enter the horse back riding game. Beat a score of 1000 for a heart piece, and then beat 1500 for the next quiver upgrade, enabling you to carry another 10 arrows.
Wallet Upgrades
Upgrade 1: Adult Wallet -200 Rupees--This upgrade can be gotten in the House of the Skulltula's in Kakariko Village. After you have defeated 10 golden skulltula's, talk to the first man on the right. He will give you the Adult's Wallet which lets you hold 101 more rupees than your previous capacity of 99.
Upgrade 2: Giant's Wallet -500 Rupees--This upgrade can also be gotten in the House of the Skulltula's in Kakariko Village. After defeating 30 Golden Skultula's talk to the 2nd man on the right to get the Giant's Wallet, allow you to hold a whopping 500 rupees, which is an amazing 300 more than the adult wallet's capacity.
*Any upgrades not stated here have been deemed items and are displayed on the Items and Weapons page