I believe there is no support for multi-dimensional examples tables in Gherkin scenarios as you have described. Also keep in mind what BDD is largely for: being readable to the business. We developers have to be careful not to get too technical in the feature files ;)
That being said, I can think of a couple ways to solve this problem.
1.Write either the site or the search_str multiple times like:
Examples:
| site | search_str |
| google.com | pierce brosnan |
| google.com | matt leblank |
| google.com | jeff goldblum |
| jeeves.com | matt leblank |
etc...
2.Write the gherkin separately for each site like:
Given I visit "google.com"
When I enter <search_str>
Then I see at least 1 result
Examples:
| search_str |
| pierce brosnan |
| matt leblank |
| jeff goldblum |
3.Table after one of the steps along with examples like:
Given I visit <site>
| site |
| google.com |
| jeeves.com |
| duckduckgo.com |
When I enter <search_str>
Then I see at least 1 result
Examples:
| search_str |
| pierce brosnan |
| matt leblank |
| jeff goldblum |