I tried a really quick build with the 5534 before I had to leave for work, and I'm sure I'm doing something wrong somewhere, maybe too much gain?? I set the resistors at 1k for the Input resistor and 100k for the feedback resistor to try to get some more voltage.
A gain of 100 seems about right, but with acoustic audio you always need a gain control or a volume control. From what I've read, an SM58 is not a particularly sensitive mic, but it can put-out nearly 1V if you stick it directly in front of a kick drum...
All I got was just a bunch of noise, no signal. I didn't have the first cap on hand, so I didn't use it... Could that have caused my problem?
Yes, that could be a problem, especially with a single-supply. The mic will kill the bias (half the supply voltage) and you are putting DC voltage into the mic. It's unlikely, but you can potentially damage the mic by doing that! (Phantom power used by studio condenser mics is applied common-mode between the signal lines and ground, so that the mic won't get damaged, even if you connect a dynamic mic, which doesn't use phantom power.)
Today I was using an SM58.
I assume that has an XLR connector? It's also possible that your mic is connected incorrectly. All studio/performance mics use a balanced (3-wire) connection. A proper microphone preamp will have a balanced [u[/u]](Operational amplifier applications - Wikipedia) input. (Sometimes, a transformer is used in place of a differential amplifier.) If you need high-quality audio, you should use a proper mic preamp with the proper low-impedance balanced input.
If you are simply running the audio into the Arduino and you don't need a clean low-noise signal, you can get-away with connecting one of the signal lines to ground. In any case, you need to connect all 3 wires coming from the mic.
P.S.
If you are running the preamp-output into an Arduino, you need to protect the Arduino input from negative voltages and/or positive voltages greater than 5V. (You can do that with a resistor and a pair of diodes.)