How to add Header Search in Madison theme?

You can enable it in Appearance/Customize/Header Search tab. Full width Header Search will be easily accessible under the top Menu on all pages. You will have ability to set up 4 fields with different Search Inputs.

Note! Search Input settings for those attributes should be the same as in your settings in Properties/Settings/Developer tab.