You're right that it's subtle to figure out how to get search results in Gmail. Even the obvious step of going to the "Trash" folder then doing a search results in searches that are showing the results everywhere but your Trash folder!

To figure out how to search your deleted messages, you need to have eagle eyes and really pay attention to the grayed-out text in the search results. Here, let me show you. I'll do a search for "mac os x" in my Gmail folder by entering that text in the search box:

Click on "Search Mail" and you'll get search results:

This can go on for quite a ways, but the critical thing is to scroll to the bottom, where you'll see:

Notice the area I've circled, where it says "Deleted messages match your search" then has a link to View them. Click that and you'll have successfully found the results of your search in your deleted message folder in Gmail.

Of course, you can take the geeky way too, click on "Show search options" and you'll see a far more sophisticated set of filters for a search:

The "Search" "All Mail" has the option of limiting your search to just "Trash" or, the most useful, "Mail & Spam & Trash". A bit more complicated, but if you want to move into the world of power Gmail users, that's the path to get there!