I figured out the answer from the UISearchDisplayController documentation - when displayed in a navbar, the navbar uses the Search controller's navigation item instead of it's own. The default title for that item is Search.
Setting self.searchDisplayController.navigationItem.title = @"MY TITLE" worked.