Ocarina of Time
Link can get both upgrades to the Bomb Bag by either stopping the rolling Goron (Hot Rodder) while he is beneath the overhang. Link can also receive both upgrades as rewards at the Bombchu Bowling Alley.
After saving the Old Lady's Bomb Bag from being stolen while as a Hylian, she rewards Link with an upgrade. The Business Scrub in Goron Village sells Link the largest Bomb Bag upgrade for 200 Rupees if Link is in Goron form.
The Business Scrub sells Link both upgrades for 200 Rupees each, but it is better to receive the first upgrade for free, and then save the Old Lady again on a different cycle to obtain the Blast Mask for free.
The Wind Waker
The Minish Cap
The Bomb Bag can be found in Minish Village after completing Deepwood Shrine. After speaking with the Minish Elder he will open a nearby path. This path will lead to a house containing a Minish who will give Link the Bomb Bag, hearing of his heroic actions. Bombs are used to defeat enemies, blow holes in the ground, and blow up cracked walls.
Zora's River Bomb Bag
Molten Shard Bomb Bag
After the Twilight has been cleared from the Lanayru Province, Link can blow up the Molten Shard dropped into the Zora's Throne Room earlier to defrost Zora's Domain. A rather confused Goron comes out and thanks Link with a Bomb Bag.
Giant Bomb Bag
After helping Iza with her problem, Link can go back to her and go on her boating ride and score at least 25 points in the mini-game. If Link does so, he will be rewarded with the Giant Bomb Bag. This bag, despite its name, is not a regular bag that can hold double the number of bombs; but instead, it doubles the amount of bombs all Link's Bomb Bags can hold.
The original Bomb Bag can be found in the Temple of Wind. It can only hold 10 bombs.
After obtaining the Bomb Bag, the Cannon Game Challenge mini-game becomes available on Bannan Island. Scoring over 2,500 points rewards Link with a Bomb Bag upgrade, allowing him to carry 20 bombs. The next upgrade can be purchased from Beedle. He sells it to Link for 1,000 Rupees. This allows Link's Bomb Bag to hold 30 bombs.
Link can purchase the Bomb Bag for 500 Rupees at Beedle's Air Shop. It allows Link to carry 10 bombs.
After obtaining the Whip, Link can participate in the Whip Race. Finish in under 1:30 to be awarded the first upgrade, allowing Link to hold 20 bombs. Clear the second Take 'Em All On challenge for another upgrade, increasing the bag's capacity to 30 bombs.
In Skyward Sword, the Bomb Bag is found in the second dungeon, the Earth Temple. Ledd the Mogma tells Link he has dropped his Bomb Bag when some monster scared him. Enter the next room and Link fights the dungeon's mini-boss, two Lizalfos. The reward for defeating them is Ledd's Bomb Bag. However, when Ledd learns Link is searching for Zelda, he decides to give it to Link, and also throws in five bombs as a bonus. It is unknown how he carried the bombs even after losing his Bomb Bag. Link can refill it to ten using nearby Bomb Flowers, which he can store in his bag after picking them up.
In Skyward Sword, there are no "traditional" upgrades to the Bomb Bag. To enhance it, Link can purchase an additional Bomb Bag at the Gear Peddler's shop in the Bazaar, or he can wait to get one in a Goddess Chest. Once Link has the Small Bomb Bag, carrying it in his Adventure Pouch allows him to carry 5 additional bombs. Link can also upgrade it at the Scrap Shop to the Medium and Large Bomb Bags, which hold 10 and 15 bombs respectively.
Additional Small Bomb Bags can be purchased to further increase the capacity, though they each take up a slot in Link's Pouch; thus, Link cannot carry more than 8 additional Bomb Bags at any time in the game. This results in a maximum Bomb capacity of 130 bombs, although this requires the Adventure Pouch to be emptied of all other items.
If Link leaves his additional Bomb Bag(s) at the Item Check, they will no longer count towards his maximum bomb carrying capacity.