A lot of people create a bank alt that they can send the stuff that might be useful or worth auctioning. When you get to a mailbox, you just send all of your extra non-soulbound stuff to the bank alt so you can keep playing. You can then sort out what to do with it later.
A few more details on early bag options:
(1) Each of the city factions will sell you a 16 slot bag for less than 2g once you get to revered with the faction. They are unique so you can only use one from each city, but they are generally the cheapest option per bag slot. (There are 7 city factions, so you can get up to 7 of the bags — although you’ll usually have enough gold to move onto other options before you get revered with all the cities.)
There’s a quartermaster for each city faction, and they are usually NPCs sitting on mounts near the flight masters in the cities. For Horde, Silvermoon is near the flight master just outside Silvermoon’s gates. The Thunder Bluff quartermaster is right next to the flight master inside the totem in Thunder Bluff. In Undercity, it’s near the flightmaster in the center of the city. The Darkspear, Ogrimmar, and Bilgewater quartermaster are all near Orgrimmar’s flightmaster that’s up on the mesa in the middle of town. The Huajin Pandaran is the main exception to the flightpath rule. It’s actually in the Valley of Honor in Orgrimmar. Look for the red hot air ballon. The NPC is near there.
Those quartermasters will also sell you special tabards for their city. If you wear them while doing a dungeon, you’ll get extra rep for that faction.
(2) You can get a “free” 16 slot bag from the Darkmoon Faire. The Darkmoon Faire is an event that runs for a week starting on the first Sunday of the month. You can look at the in game calander to see when it is up. You can buy a 16 slot bag for one Darkmoon Faire prize ticket when it’s up. (You earn tickets through the various activities on the Island, and the initial quest to go to the Faire will give you 5 tickets.) It’s unique, so you can only have one.
(3) Hit up the Auction House. The specific bag you’ll want to look for is “Netherweave Bag.” These tend to be the cheapest per bag slot on the AH. (Netherweave drops like crazy, and making bags is pretty much the only thing to do with it that can beat just vendoring it so lots of people with tailoring tend to make them.) As it’s the AH, prices will vary, but you can usually pick them up for 5-10g each. If they are higher than that, hold off on buying and keep any eye out. They don’t usually stay high for very long.
(4) If you’re just really desperate for anything, you can buy some 6 or 8 slots bags for a few silver from vendors in various cities. (Some general goods vendors have them, and there’s a bag vendor in Orgrimmar in The Drag.) They’ll often sell other bags as well, but they’ll tend to be more expensive per bag slot that the other options mentioned above.