EDIT - Aug 12, 2011
I didn't realize you wanted to go from device to device with the audio. You can always use CFNetwork and simply socket into a device. The trick is going to be detecting it. Look into bonjour services as well. You will still need to use AudioToolbox to process the audio into buffers and through either bonjour or a socket.
End edit
@greg AVFoundation gives you things like AVAudioRecorder, but it doesn't quite let you stream out packets like he wants.
I'd take a look at AudioToolbox. If you use an AudioQueue, you can specify a format for streaming. Then, add an input queue callback and you get access to the raw packets of recorded audio.
Take a look at iLBC for a codec. It has a small enough footprint to let you do everything over 3g.
Here's a great apple reference on AudioQueue programming:
http://developer.apple.com/library/mac/#documentation/MusicAudio/Conceptual/AudioQueueProgrammingGuide/AQRecord/RecordingAudio.html
Good luck!