You should go to your adsense account and get the code. Then go to your blog. I use blogger, I just have to go to the option "add HTML" and paste the code in there. Your platform should have something similar. That's all
If you're using Wordpress 2.7+ following the steps below will add the search box to your sidebar. (Before you do anything you must get the Search Bar code from your adsense account. Once that's done proceed to the steps below) 1. Go to your wp-admin page. 2. Click "Appearance". 3. Click "Widgets". 4. Click the "Add" link next to the widget titled "Text" 5. Click "Edit" on the "Text" widget in the "Current Widgets" 6. Paste the copied code from adsense and click "Done" 7. Hit "Save Changes" at the bottom of the "Current Widgets" sidebar. Done! Hope this helps.
As far as i know you dont need a plugin. Just a template that allows the use of widgets. If you're using 2.7+ the text widget comes preinstalled. Also, another way to do it would be to edit the sidebar.php and simply paste the code in there. Because html is supported inside php files. (this would probably be the best way)