1. Choose the All Mail folder
  2. Check the select box to select all emails. 

    You can also select "Read", "Unread", "Starred", "Unstarred" by clicking on the small arrow to the right of the checkbox

  3. Click the Select all X messages in All Mail link (where X is the number of emails displayed).
  4. Click the Trash icon