In Outlook 2010 and some email, you can set Outlook to automatically move the deleted items to [Gmail]/Trash folder on the server. To do so, go to the “Account Settings” of the Gmail account, and change its account settings. At “More Settings”, go to “Deleted Items” tab, and select “Move deleted items to the following server on the server”, and select the “[Gmail]/Trash” folder in the tree list.
An email message in Outlook can appear in many folders (applied with many labels). Typically, once you delete the email and move it to Trash, the email should be removed from other folders by Gmail too. Perform a sync or Send/Receive All Folders (for Outlook) so that mail client can synchronize the change that takes place on Gmail cloud after deletion. If for some reason Gmail and mail client does not automatically remove to Trash a delete email from all folders (labels), and the supposedly deleted emails on folders other than Trash folder, then manual deletion from each and every folders is requires. This including from [Gmail]/All Mail folder which archived all mails.
Once the e-mails are moved to Trash folder, it will be automatically purged by Google server process after 30 days. You can also configure your mail client to process purge permanently items mark as trashed or deleted in the original folder automatically from the server. Note that also if you delete any email message from [Gmail]/Spam or [Gmail]/Trash, it will be deleted permanently, locally and on Gmail server.