Good god, I actually have something to contribute to this discussion that hasn't actually been said before! (Don't worry, I'll also repeat a lot of other people's opinions.)
As far as army&navy and thrift stores go, yes, yes, yes!
BUT! Don't trap yourself into thinking the clothes there are anything more than pieced together pieces of fabric. There are some absolutely hideous dresses, suit sets, and more that are huge and can very satisfactorily be hacked into skirts, vests, corsets, WHATEVER. Especially great: the 80's black velvet prom dress. You can get yards of nice black velvet from one of these that makes for a delicious corset (I say this from experience).
A different kind of thrift store is a little charity organization called Habitat for Humanity. Their mission is building affordable housing through community labor. Great organization, but I personally love them not because of their mission, but because of their ReStores.
This charity sets up thrift shops for building materials, and it is a steampunker's paradise. The plumbing section is filled with funky brass tubing and pipery. The hardware section has unidentifiable bolts, nuts, bits and bobs, as well as old drawer-pulls that are basically just pieces of sturdy brass filigree. They have oddly-shaped hinges. They have curtain rods with big glass chunks on the end. They have blades from ceiling fans which were crying out quietly to me to be made into a collapsible wing set for a jet-pack.
If nothing else, the stuff you find there could be sold to other people online as "steampunk supplies" for 10x the price.
http://www.habitat.org/restores/ <-- here's the link for finding your local store. Looks like mainly US and Canada. Sorry, you Brits, but we don't get car boot sales here in the States, so we're even now.
---
FINDING CHEAP BROCADE AND LEATHER FOR SEWING
Many fabric stores sell upholstery fabric, and many fabric stores also have heaping piles of discount fabric that nobody ever bought, which usually consist at least partly of said upholstery fabric. At my local fabric store, I have a good selection of brocade and fake suede for $4.99 a yard on any day of the week.
Upholstery stores also almost always sell remnants, and here is where your $5 leather spats, corsets, toppers, bracers, satchels, and whatever else you can dream up are born. It's not (as far as I know - I really don't see how it could be) real leather, so no baby aminals will be without their mommies because of it. It's good quality, and waterproof, and necessarily durable. It's thinner than most real leather, and therefore easier to sew. I've yet to attempt ironing on any interfacing to stiffen it up, so I don't know how it reacts to heat.
Upholstery stores also carry some interesting scraps of brocade. Let me clarify when I say scraps: I for $5 each, I got a 56" x 25ish" piece of gorgeous turquoise, gold, and brown brocade, a 58" x 26ish" piece of gorgeous warm medium brown upholstery leather, and a 54" by 23" piece of dark brown upholstery leather, which is also gorgeous.
Any of these pieces by itself is big enough to make boots, a bustle, a corset, a lab apron, or a travel bag. I'm going to combine pieces of each to make a corset with a matching bag. (Don't hold your breath for photos, though; I'm getting married in June, and sewing my wedding dress takes priority.)
---
Also, hardwareelf.com has some great alternatives to gears for steaming up outfits. Check these out:
Hope this reply isn't too long. I just joined the site and I'm way excited!