How to perform decryption in this single-bit PKE scheme?
To decrypt, you basically take the $g^y$ component and raise it to the secret key, obtaining $g^{yx}$. Now, if this value is equal to the second component of the ciphertext, you can see that $M$ must be 0, since $g^{yx} = h^y$; otherwise, $M$ is 1. 

Regarding the proof: yes, it would be very similar to ElGamal, since you have to construct the challenge ciphertext using a DDH tuple.