one could use a switched capacitor bandpass filter IC and scan through the frequencies of the audio spectrum. If one is specifically dealing with music there are 120 distinct musical notes in the audio spectrum, and only 22 distinct notes on any one string of a guitar. You wouldn't be able to tell what string you're on by the frequency alone because many notes appear on the guitar neck in more than one location, IE playing the low-E string open is the same as playing the A string at the 5th fret.
The audio spectrum from 0 octave to 10th octave goes from 16.35Hz to 15804.27Hz. With standard tuning a six string guitar ranges from E2 (82.41Hz) to D6 (1174.66Hz). The formula for the individual note frequencies can be found here: Note - Wikipedia.
The Q required for 1/12 octave resolution (individual note resolution) is 17.31. The entire note range of a standard guitar not including duplicates is only 46 notes. You could conceivably scan every note on the guitar and only need 92 bytes to store the ADC conversions of each note, and that's if you don't use complicated code to kill dead memory space between the extra 6 bits not being used when you store an ADC conversion. You could even double buffer the notes and still only use 184 bytes for ADC conversions.
You would simply set the Q and center frequency of the filter IC and sample the audio, though I'd recommend using a circuit like the one macegr posted at http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1216393384/6 between the filter IC and the arduino to bring the audio to a usable level.
That all being said, then the idea is to simply scan through a mere 46 frequencies, which is about 1/3 of the entire audio spectrum. The arduino is not capable of 44khz sampling rate, but 10khz is doable not accounting for how long it takes to setup the bandpass filter between note reads.
If you really feel limited by the 1k of ram in the arduino as I did, you could get a sanguino (assuming there are any kits available again yet). 64k of flash and 4k of ram. I'm working on a 115 band audio spectrum analyzer project and using the sanguino for it. I'm planning to sample my audio for the display using the method I've described here.
Also, considering that the highest note on the guitar is only 1174.66Hz at standard tuning you could use the counters in the arduino to measure the frequency, but that would only work for one note at a time. It wouldn't work for chords.