Short answer: It's not possible on any mail client worth its salt.
Mail clients are designed to do one thing: display text. They're good at that, and even at displaying images, but asking them to submit a form to your website is a bad idea. Even if most of them didn't block this behavior (which they do) users aren't used to doing a search from an e-mail, and would probably be suspicious of clicking textboxes and buttons in your email, as they should be. Even if they do figure this out, you're opening them to a wide range of vulnerabilities, including someone spoofing the email and pointing the form to their own server, then asking the user to "log in" and stealing their credentials.
If the search page on your website uses GET to parse user input, you should be able to put a link in your newsletter to display a specifically crafted search.
for example, your newsletter could look like the following:
Hi everyone, We now have awesome blue widgets in stock! Big ones, little ones, square ones, round ones, and double super awesome ones. You can view the widgets at: http://www.example.com/search.php?name=widget&color=blue