AudioRecord is an Android class that lets you record audio and fiddle with it in real time. MediaRecorder is what you want if you'd rather save the audio to a file and deal with it later.
You'll notice that AudioRecord's constructor takes 5 parameters: audioSource, sampleRateInHz, channelConfig, audioFormat, and bufferSizeInBytes. audioSource is reasonable enough; I used MediaRecorder.AudioSource.MIC. For bufferSizeInBytes, you can use the getMinBufferSize() function. (then you might want to multiply the result by 5 or 10 or something.) But the other 3, you kind of have to guess.
I dealt with this for a while, found something that worked on my Nexus One (2.2), launched an app, and then found out that it crashed the Droid (2.1-update1) on startup. So to save you all a similar experience, here's what I know:
44100 hz, AudioFormat.CHANNEL_IN_MONO, and AudioFormat.ENCODING_PCM_16BIT is the one and only configuration guaranteed to work on all phones. The Android Compatibility Test Suite (that phone makers have to run their phones through before they release them) guarantees this (see AudioRecordTest).
Sample rates of 44100, 22050, 16000, 11025, and 8000 hz (and probably others) work on the Nexus One and Droid. Annoyingly, only 8000 hz works on the emulator (2.1-update1), and by "works", I mean "doesn't crash". I haven't tested that it actually records anything useful.
CHANNEL_IN_STEREO works on the Nexus One, but not on the Droid.
This is all correct as of ... about a month ago. Hopefully nothing drastic has changed since then. Make sure you've put the right permission (RECORD_AUDIO) in your AndroidManifest.xml, and good luck recording audio!