IMAP support is coming very soon. Engineers are working on the code, now. It's a more difficult task than people would imagine because the implementations of the IMAP standards by some clients (like Outlook) is a bit... "interesting".
How would this IMAP implementation work? Some kind of local proxy that does the decryption on-the-fly?
Since they use GPG internally I would imagine it simply presents GPG-encrypted mail to you and relies on the client having GPG support.
Yes, exactly. The client is able to install and run a local proxy/translator application on their machine (currently, it's called a "bridge"). Their IMAP client connects to it and it interacts with ProtonMail's APIs over HTTPS. Since the bridge runs locally, the private key is locally decrypted with the client's password. The password is never sent to the server. The decryption takes place locally in the bridge software running on the client's computer.