I was just stumbling around EE Stack and found this post: What protocol does a headphone jack use. And it sparked some curiosity in me, and I figure, if the iPhone can do it, I want to as well.
Does any one know of any projects that are doing this now or whether or not it's even possible?
UPDATE
RIP
You are basically asking how to turn the microphone input into a modem input. A variant of this clever technique is used commercially by Square for their magstripe readers on both iOS and Android devices.
To do so requires getting access to the raw PCM stream from Android and decoding the input. Luckily for you, someone has already done it and thrown the source out there. See this Hack a Day linked project for sample Arduino and Android code for transmitting only.
I couldn't find example Android code to receive, but there are rather extensive notes on doing FSK with iOS in this Arduino forum post.
(Though it wasn't your question, an easier way to get data in and out of an Android device is the new USB Host and Accessory support. It requires a newish phone and OS, so not as flexible as the audio route.)