This is a no-brainer really.
The 36kHz is the carrier frequency, the baseband signal is well within the audio range. Use an integrated RC receiver, it would be silly to make your own. They combine AGC, bandpass filter and demodulator.
I've used Vishay devices, and I'm quite satisfied with them.
There's a number of protocols, but RC-5 is the most used, so I'll take that as an example. RC-5 uses Manchester coding, with a bit time of 1.778ms, so that the lowest frequencies are 281Hz and 562Hz resp.
That's well within the audio band, including quite some harmonics, so low-pass filtering it at 20kHz, or even 10, doesn't harm the signal's integrity, and you'll be able to detect edges. The image shows an 889\$\mu\$s pulse plus ditto pause, giving the higher frequency of 562Hz, cut off at 10kHz.
Mobile phone voice bandwidth is limited to 4kHz, however, and since the microphone input is primarily meant for voice input that limit may apply already here. You can play MP3 quality audio with it, but I don't know if you can record it as well. Anyway, with a worst case brick wall filter at 4kHz that same signal will look like this:
Still no problem; you can easily pass the signal through a comparator when sampling and you'll get perfectly timed edges.
That's it really. Connect the output of the RC receiver to your phone via a resistor divider to bring the logic level signal down to mic level. If your receiver works at 3.3V the output level will be about 60dB above 2mV RMS microphone level. In that case use a 70k\$\Omega\$ resistor (for a total of 100k\$\Omega\$, the pull-up in the receiver is already 30k\$\Omega\$) in series with a 100\$\Omega\$ resistor to scale the RC signal down. YMMV.
trivia
The 14 bits commands repeat with 50 bit time pauses for a total period of 64 bit times, so that the repetition frequency is around 9Hz. The baseband signal is sometimes used directly to blink a visible light LED.