advanced search - mailing fields not present
look in civicrm/admin/setting/preferences/display?reset=1

This is a bit counter-intuitive since the first place most would look is under Search Preferences - but it lives under Display Preferences as it is about what displays on the search screen. hth