How to Change Pivot Header Template in Windows Phone 8

EDITED for WinRT (sorry for the delay and thanks for the reminder to update this answer): To edit a full template right click on the control when in Document Outline and select Edit Template - Current (in Visual Studio or Blend) and the template will be generated for you and you can edit as you want, see my answer here for screenshots.

Here are the two examples below (posted in 2013) redone for Windows Phone Windows Runtime:

<Grid Background="Transparent">
    <Pivot Title="Re-templating example">
        <Pivot.HeaderTemplate>
            <DataTemplate>
                <Grid Background="Blue">
                    <TextBlock Text="{Binding}" />
                </Grid>
            </DataTemplate>
        </Pivot.HeaderTemplate>
        <Pivot.TitleTemplate>
            <DataTemplate>
                <Grid Background="Green">
                    <TextBlock Text="{Binding}" />
                </Grid>
            </DataTemplate>
        </Pivot.TitleTemplate>
        <PivotItem Header="One">
            <TextBlock FontSize="35"
                        Text="This is item one" />
        </PivotItem>
        <PivotItem Header="Two">
            <TextBlock FontSize="35"
                        Text="This is item 2" />
        </PivotItem>
    </Pivot>
</Grid>

And second example, notice that we are wrapping the ContentPresenter in a Grid (you could use a border as well or any other element):

<Page.Resources>
    <SolidColorBrush x:Key="PivotBackground" Color="#FFE46C08"/>

    <Style x:Key="PivotStyle" TargetType="Pivot">
        <Setter Property="Template">
            <Setter.Value>
                <ControlTemplate TargetType="Pivot">
                    <Grid x:Name="RootElement" HorizontalAlignment="{TemplateBinding HorizontalAlignment}" VerticalAlignment="{TemplateBinding VerticalAlignment}">
                        <Grid.RowDefinitions>
                            <RowDefinition Height="Auto"/>
                            <RowDefinition Height="*"/>
                        </Grid.RowDefinitions>
                        <!--Notice that ContentControl is wrapped in a Grid and Background set to resource furtehr up-->
                        <Grid VerticalAlignment="Center" Background="{StaticResource PivotBackground}">
                            <ContentControl x:Name="TitleContentControl" ContentTemplate="{TemplateBinding TitleTemplate}" Content="{TemplateBinding Title}" Style="{StaticResource PivotTitleContentControlStyle}"/>
                        </Grid>
                        <ScrollViewer x:Name="ScrollViewer" HorizontalSnapPointsAlignment="Center" HorizontalSnapPointsType="MandatorySingle" HorizontalScrollBarVisibility="Hidden" Margin="{TemplateBinding Padding}" Grid.Row="1" Template="{StaticResource ScrollViewerScrollBarlessTemplate}" VerticalSnapPointsType="None" VerticalScrollBarVisibility="Disabled" VerticalScrollMode="Disabled" VerticalContentAlignment="Stretch" ZoomMode="Disabled">
                            <PivotPanel x:Name="Panel" VerticalAlignment="Stretch">
                                <!--Background set to resource further up-->
                                <PivotHeaderPanel Background="{StaticResource PivotBackground}" x:Name="Header" >
                                    <PivotHeaderPanel.RenderTransform>
                                        <CompositeTransform x:Name="HeaderTranslateTransform" TranslateX="0"/>
                                    </PivotHeaderPanel.RenderTransform>
                                </PivotHeaderPanel>
                                <ItemsPresenter x:Name="PivotItemPresenter">
                                    <ItemsPresenter.RenderTransform>
                                        <TranslateTransform x:Name="ItemsPresenterTranslateTransform" X="0"/>
                                    </ItemsPresenter.RenderTransform>
                                </ItemsPresenter>
                            </PivotPanel>
                        </ScrollViewer>
                    </Grid>
                </ControlTemplate>
            </Setter.Value>
        </Setter>
    </Style>
</Page.Resources>

Using the above style:

<Grid Background="Transparent">
    <Pivot Style="{StaticResource PivotStyle}"
            Title="Re-templating example">
        <PivotItem Header="One">
            <TextBlock FontSize="35" Text="This is item one" />
        </PivotItem>
        <PivotItem Header="Two">
            <TextBlock FontSize="35" Text="This is item 2"/>
        </PivotItem>
    </Pivot>
</Grid>

By the way, it's usually preferred to keep styles in a separate style file- I've only kept them on the same page for simplicity for this example. If you remove the x:key attribute the style will be applied to all the controls of the set target type (Pivot in this example).

Answer from 2013 for Windows Phone 7.X and Windows Phone 8 (WP Silverlight:

There are a few ways you can do it, but here is one example:

<Grid x:Name="LayoutRoot" Background="Transparent">
    <Grid.RowDefinitions>
        <RowDefinition Height="Auto"/>
        <RowDefinition Height="*"/>  
    </Grid.RowDefinitions>

    <phone:Pivot Grid.Row="1">
        <phone:Pivot.HeaderTemplate>
            <DataTemplate>
                <Grid Background="Red" Height="200">
                    <TextBlock Text="{Binding}"/>
                </Grid>
            </DataTemplate>
        </phone:Pivot.HeaderTemplate>
        <phone:PivotItem Header="Test">
            <TextBlock Text="ghjgb"/>
        </phone:PivotItem>
        <phone:PivotItem Header="Test">
            <TextBlock Text="ghjgb"/>
        </phone:PivotItem>
    </phone:Pivot>

If you however want to do this:

You can do this, remove the x:key to apply to all pivoits, or use the key to set the style on just selected pivoit elements like so:

<controls:Pivot Title="The Marathon Runner" Style="{StaticResource PivotStyle}">
    <Style x:Key="PivotStyle" TargetType="phone:Pivot">
        <Setter Property="Margin" Value="0"/>
        <Setter Property="Padding" Value="0"/>
        <Setter Property="Foreground" Value="{StaticResource PhoneForegroundBrush}"/>
        <Setter Property="Background" Value="Transparent"/>
        <Setter Property="ItemsPanel">
            <Setter.Value>
                <ItemsPanelTemplate>
                    <Grid/>
                </ItemsPanelTemplate>
            </Setter.Value>
        </Setter>
        <Setter Property="Template">
            <Setter.Value>
                <ControlTemplate TargetType="phone:Pivot">
                    <Grid HorizontalAlignment="{TemplateBinding HorizontalAlignment}"
      VerticalAlignment="{TemplateBinding VerticalAlignment}">
                        <Grid.RowDefinitions>
                            <RowDefinition Height="Auto"/>
                            <RowDefinition Height="Auto"/>
                            <RowDefinition Height="*"/>
                        </Grid.RowDefinitions>
                        <Grid Background="#ff9000" CacheMode="BitmapCache" Grid.RowSpan="2" />
                        <Grid Background="{TemplateBinding Background}" CacheMode="BitmapCache"
        Grid.Row="2" />
                        <ContentPresenter ContentTemplate="{TemplateBinding TitleTemplate}"
                    Content="{TemplateBinding Title}" Margin="24,17,0,-7"/>
                        <Primitives:PivotHeadersControl x:Name="HeadersListElement"
                                          Grid.Row="1"/>
                        <ItemsPresenter x:Name="PivotItemPresenter"
                  Margin="{TemplateBinding Padding}" Grid.Row="2"/>
                    </Grid>
                </ControlTemplate>
            </Setter.Value>
        </Setter>

Dont forget to use:

xmlns:phone="clr-namespace:Microsoft.Phone.Controls;assembly=Microsoft.Phone"
xmlns:Primitives="clr-namespace:Microsoft.Phone.Controls.Primitives;assembly=Microsoft.Phone"