If you haven't already enabled IMAP in Gmail, open up the settings page and choose Forwarding and POP/IMAP, and then select to Enable IMAP.
Open Windows Mail and choose Tools Accounts from the menu and then click on the Add button.
You'll want to select E-mail account and move to the next screen…
Enter your name.
Enter your email address, using your Gmail email address here.
Finally, more than one option on the wizard page… choose IMAP from the drop-down, and then enter in the following values:
Incoming Server: imap.gmail.com
Outgoing Server: smtp.gmail.com
Check "Outgoing server requires authentication"
Note: If you are outside of the US you may need to use imap.googlemail.com and smtp.googlemail.com instead of imap.gmail.com and smtp.gmail.com.
On the next screen enter in your Gmail email address and your password.
Very important: Check the box for "Do not download my e-mail and folders at this time".
Click the Finish button to get back to the Internet Accounts dialog, and then select your new account and choose the Properties button.
On the Advanced tab, you'll want to first check both options for "This server requires a secure connection(SSL)", and then verify that the ports are set to the following:
Outgoing mail (SMTP): 587
Incoming mail (IMAP): 993
Now choose the IMAP tab and remove the checkbox for "Store special folders on IMAP server".
Informative Note: If you do not remove the checkbox here you will end up with duplicated sent items, and your deleted / junk mail will just end up being archived in a label. Your choice. If you don't use labels in Gmail you could enter [Gmail] as the root folder path, and then adjust the values in the special folders section to match the Gmail folder names. It's also worth noting that you cannot use [Gmail]Spam here because Windows Mail will not accept the "" or "/" characters in folder names.
Now you can close out of the account settings dialogs, but before you start Sending/Receiving you'll probably want to click on the "imap.gmail.com" item in the left hand folder pane and adjust these settings so Windows mail doesn't try and download everything:
Remove the checkbox from [Gmail]
Remove the checkbox from [Spam]
If you have a lot of messages, you should consider removing the checkbox from [All Mail]
Change all other folders to "Headers only". (You could leave the Inbox set to All if you'd like)
Now that you've made these changes, you can go ahead and hit the Send/Receive button, and hopefully everything should work perfectly now.