Should we use fieldset even for one search box input? Which we use in header of the site usually?
No. There is no point in using fieldset elements unless you are dividing the form up into logical sets of fields.
It is excellent for (for example) marking up a set of fields for delivery address and some nearly identical ones for billing address. If you can't make sets (plural) don't use a fieldset element.