Brian's right that egg cartons will do nothing in the way of soundproofing. Some think that they do offer some diffusion characteristics, though ... and I think that's what Charlie was getting at. I don't know if I really believe it or not though ... but then again, I've never been in a studio that ever used egg cartons so I really don't know first hand.
Also, I don't think the issue Josh is having really deals as much with soundproofing as it does with acoustic control.
I do know that a fully stocked bookcase (with different sized books in it) can also act as a good diffusor of sound waves. But it won't absorb anything.
For absorption, you need some kind of mass that will translate the acoustic energy into thermal energy. Foam works really well for high frequency absorption, but not as well for mid to low frequencies. There are some foam products designed to soak up low frequencies that tend to build up in the tetrahedral corners of a room. Those products are expensive, though.
The problem with foam is that it's almost always a permanent addition to the room ... the adhesive used to mount it will ruin the foam if you try to remove it. It's also a significant enough investment to want to take it with you if you ever move. Auralex now markets plexiglass plates that you can mount the foam onto and then secure those to the wall using velcro fasteners. A really great idea ... but I would imagine even more expensive.
I'm extremely budget-minded as well, and I've come up with my own plan for mounting foam in my studio. I've recently ordered some foam with the plan of adhereing it to some poster-board frames (oh about 2'x3' - just the back cardboard piece, though) and then hanging it like a picture. These posterboard frames can be purchased at Target/KMart/WalMart/etc. I don't know how successful that will be ... but it's a plan nonetheless. I'm getting the most cost-effective foam I could find,
Markerfoam which is about 80¢/sq ft. Who knows if it's good or not ... but I'm giving it a shot ... it's a $20 leap of faith.
But, like I said, you also want to control the mid and low frequencies. I'm still doing research on solutions for that, though. Some good resources are John's site (which I can't remember the url offhand for ... but check some older posts in this forum for it) and auralex.com (they have a great "Acoustics 101" pdf). Both will give you a better understanding of acoustics in general and maybe some ideas on how you can make something of your own that will be effective.