I am new to hardware hacking in general. I have a Gumsitx Overo Earth COM and a Palo35 expansion board with audio in/audio out capabilities. According to Gumstix's wikipage on audio input, the Palo35 board has "stereo audio in," but not a "stereo headset jack." I know that I am going to need an amplifier if I want to add a microphone, but I am not sure how to actually integrate an amplifier or microphone onto the board. I have searched for answers on Google for how to do this but I have not found many helpful results.
The Overo COMs have line-level inputs and outputs. You're right that if you want to drive anything other than a line in on a stereo or amplified speakers, you will need to hook up an amplifier. It can be as simple as a little transistor amplifier or LM386 op-amp, or as complex as the guitar amp on "Back to the Future." :-)
Adding a microphone input to the COM will also need an amplifier, as you've already mentioned. If you just want to get up and running quickly, I suggest something like this SparkFun kit; it's only mono, but you can connect both the left and right inputs of the COM to the output of this without trouble.