Weapon upgrades are not so important that you should spend all your time trying to upgrade everything as soon as possible. They're nice, but you should wait until it's easier to get the items for the higher upgrades. Find the items and upgrade at your convenience. What you really should be worrying about is collecting the strongest magic possible at low levels and junctioning it.

If you really want to upgrade everything ASAP, then you're going to have to play many card games to collect cards, and modify those cards to get the items necessary to upgrade.

The earliest possible time to get Squall's Lionheart is during the Dollet mission. I've heard that you can get Adamantine from the X-ATM092 robot after you defeat it. I've never gotten one, so I don't know the specifics about getting it. I would suggest waiting until you've gotten Minotaur's card to get the Adamantine. Other than that, you need 4 Dragon Fangs and 12 Pulse Ammo. I think high level Anacondaurs and Grendels drop Dragon Fangs. I've never done it, so I could be wrong. You'll need a total of 20 Elnoyle cards to get the 12 Pulse Ammo.

For Quistis's Save the Queen you need 2 Malboro Tentacles, 4 Sharp Spikes, and 4 Energy Crystals. Get the Malboro Tentacles by modifying Malboro cards. 40 Elnoyle cards will get you enough Energy Crystals. Modify Grand Mantis or Death Claw cards for the Sharp Spikes.

Zell's Ehrgeiz requires 1 Adamantine, 4 Dragon Skins, and 1 Fury Fragment. Modify Blue Dragon cards to get Fury Fragments.

Selphie's Strange Vision requires 1 Adamantine, 3 Star Fragments, and 2 Curse Spikes. Modify Iron Giant cards for Star Fragments, and Tri-Face cards for Curse Spikes.

The Shooting Star for Rinoa requires 2 Windmills, 1 Regen Ring, 1 Force Armlet, and 2 Energy Crystals. You plain cannot get Force Armlets until much later on in the game when you're in Esthar. The items for her Cardinal can all be gotten from modifying cards.

Irvine's Exeter requires 2 Dino Bones, 1 Moon Stone, 2 Star Fragments, and 18 Screws. Moon Stones simply cannot be found until late in the game from Imps and Elnoyles.

To modify cards, use Quezacotl's Card Mod ability in the menu. It's in the Abilities section.