The goal here is to minimize background noise as much as possible yet attain high-quality sounding audio within budget.
Pentium 4 or better.
At least 16 bit Duplex Sound Card. Duplex means you can record while playback sound. You can check this by installing Audacity->Edit->Preferences->Audio I/O->Overdub is checked, and see if it can record while playing the first track.
Ardour, for multi-track recording. In order to use the potential of your CPU, it is recommended that you install linux realtime: System->Administration->Synaptic. Check linux-rt and linux-rt headers.
Audacity, for post-production editing or mastering.
8 channels minimum is good, but the more, the better (depends on how many instruments to record simultaneously).
Analog is what I use and it's cheaper, but Digital is preferred. If analog, you may need stereo RCA cables to connect to your sound card, while digital mixers might be USB, but depends on compatibility with Linux, so you must be sure it works before you buy. The difference between the two is that analog only takes one track while digital can record more than one track simultaneously.
Nowadays, you can buy portable mixers in tight budget that sounds professional.
Microphone. Can't emphasize the importance of sound source, for this is critical of having high-quality sound. Dynamic mics are cheaper than condenser mics. The difference between the two is that dynamic mics are less sensitive to sound, therefore less background noise. Usually, condenser mics are for professional studios with good insulation.
Mic Stand. Buy a mic stand tripod, which I recommend.
Mic Cables. Be sure to buy stereo jacks, balanced cables with insulation to avoid noise. 3-5 meters is ok.