I believe that the Trash icon only shows up if you have some accounts set up to store messages that are deleted, instead of deleting them immediately.
Check in Mail's preferences under "Accounts" for your account(s) -- do you have them set up to store or keep deleted/Trash messages, or are they set to delete the items immediately?