Use ToolbarItem from YourPage.xaml.cs:
ToolbarItems.Add(new ToolbarItem("Search", "search.png",() =>
{
//logic code goes here
}));
In Xaml:
<ContentPage.ToolbarItems>
<ToolbarItem Icon="search.png" Text="Search" Clicked="Search_Clicked"/>
</ContentPage.ToolbarItems>
Update
Xamarin.Forms introduced TitleView in 3.2.0 that you can customize title of the navigation.
<ContentPage xmlns="http://xamarin.com/schemas/2014/forms"
xmlns:x="http://schemas.microsoft.com/winfx/2009/xaml"
x:Class="TestPage">
<NavigationPage.TitleView>
<Button ... />
</NavigationPage.TitleView>
...
</ContentPage>