I just finished a pretty big castle-like structure made out of stone bricks and spruce planks. That thing drained two doublechests worth of stone.
I also want to build a ridiculously large bridge over the ocean to another continent, something like 15-20 blocks wide, 2 blocks thick and with regular support beams and patterned walls. That project would keep one's stash of cobble down for a long long time...
I always "cook" my cobblestone to turn it back into smooth stone. This way, when I'm filling in spaces while tunneling and mining, I don't leave ugly cobble all over the place, and it looks natural. Weird, I know, but it just bothers me. And I have a double chest (plus more) of coal ore (that I can get tons more of coal using Fortune III pickaxe on it), and I also built a Blaze grinder (thank you Etho!!) so I have blaze rods galore as well.
And same as others, I never throw away a single item, I made a storage facility with plenty of chests and item frames to make the task easy to sort and save everything I collect.
While cobblestone is renewable, it's certainly not something you should just chuck. Unless you have a good generator set up, cobblestone generation is slower than mining.
What I would suggest doing with your cobblestone is building a mob farm. This is basically a giant, dark tower mobs spawn in. You then funnel the mobs into water and they float to a mob grinder of some kind. You can read all about that here.
Another option is to build an epic castle! You've worked that hard to gather the resources, now do something with it. If you don't like the look of cobblestone, you can smelt your stone in smooth stone/stone brick, as suggested above.
If you ever decide to play with equivalent exchange or industrial craft, cobblestone will be vital as junk you can transform.
Using the new redstone components such as hoppers, comparators and droppers, it is easy to make a large and unobtrusive cobble storage system. Put your cobble in a chest, connected via hopper to another chest, connected via hopper to another chest... for as many chests as you like, and then make a dropper item elevator to bring the cobble back to the top of the chest stack. Take cobble out of the top of the elevator whenever you need it. Now you have a huge storage area for cobble with only 2 chests you need to worry about, the cobble in chest and the cobble out chest.
I got tired of accidentally dropping items by being fumble fingered on the keyboard (and later also needed q as the "down" key for fly mod) so now it is the `/~ key instead, no more "oops" moments...
I think I'll do that. Mobs' sounds in Minecraft scare me and there were few times when I accidentally dropped my sword after getting hit from unexpected direction. I know it's silly because even Creepers can't kill me but can't do much about subconsciousness, my mind probably still remembers beta days when mobs like Skeleton could kill you.
I don't ever think I have thrown cobble away because I had to much. I drop a stack if I run out of room while mining, but otherwise it goes into chests, or gets smelted to smooth stone for stone brick. You could use some of the cobble to make a large storage room for the rest of the cobble.