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.
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.