If you can find your message by searching for it a button will appear at the top of the message. It says "Move to inbox." Click that button and the message will reappear in your inbox.

Alternately, you can select some other label from the labels dropdown and move the message into that label category.

Added: You can also find your missing message by clicking the "All Mail" folder and move it into the appropriate folder.

If you can find your message by searching for it, a button will appear at the top of the message. It says "Move to inbox." Click that button and the message will reappear in your inbox.

Alternately, you can select some other label from the labels dropdown and move the message into that label category.

Added: 
You can also find your missing message by clicking the "All Mail" folder and move it into the appropriate folder.