How to set TextBlock style for Label?

You can use a common base style for framework elements like this:

    <Style x:Key="TextBase" TargetType="{x:Type FrameworkElement}">
        <Setter Property="TextBlock.TextWrapping" Value="NoWrap"/>
        <Setter Property="TextBlock.TextTrimming" Value="None"/>
        <Setter Property="TextBlock.FontSize" Value="16"/>
        <Setter Property="TextBlock.FontFamily" Value="Franklin Gothic Medium Cond"/>
    </Style>

    <Style x:Key="TextStyleMedium" TargetType="{x:Type TextBlock}" BasedOn="{StaticResource TextBase}">
    </Style>

    <Style x:Key="HeaderBar" TargetType="{x:Type Label}" BasedOn="{StaticResource TextBase}">
        <Setter Property="Template">
            <Setter.Value>
                <ControlTemplate TargetType="{x:Type Label}">
                    <Grid>
                        <Rectangle x:Name="TitleBox" Fill="#FFECDC54">
                            <Rectangle.Stroke>
                                <LinearGradientBrush EndPoint="0.5,1" StartPoint="0.5,0">
                                    <LinearGradientBrush.RelativeTransform>
                                        <TransformGroup>
                                            <ScaleTransform CenterY="0.5" CenterX="0.5"/>
                                            <SkewTransform CenterY="0.5" CenterX="0.5"/>
                                            <RotateTransform Angle="140" CenterY="0.5" CenterX="0.5"/>
                                            <TranslateTransform/>
                                        </TransformGroup>
                                    </LinearGradientBrush.RelativeTransform>
                                    <GradientStop Color="#FFA09F9F" Offset="0.4"/>
                                    <GradientStop Color="White" Offset="0.5"/>
                                </LinearGradientBrush>
                            </Rectangle.Stroke>
                        </Rectangle>
                        <ContentPresenter HorizontalAlignment="Left" RecognizesAccessKey="True" SnapsToDevicePixels="{TemplateBinding SnapsToDevicePixels}" />
                    </Grid>
                </ControlTemplate>
            </Setter.Value>
        </Setter>
    </Style>

How do I set the Label to use the TextBlock style ("TextStyleMedium") for the text in the Label?

Set the Content of the Label to a TextBlock to which you apply your style:

<Label Style="{StaticResource HeaderBar}">
    <Label.Content>
        <TextBlock Text="text..." Style="{StaticResource TextStyleMedium}" />
    </Label.Content>
</Label>

A Label has no and creates no TextBlock by default. It's a ContentControl that has a Content property that you can set to whatever you want, including a string or a styled TextBlock.

One way of doing it is to include it as an implicit style in your ContentPresenter's Resources. Like this:

<Label Content="ABC">
  <Label.Template>
    <ControlTemplate TargetType="{x:Type Label}">
      <Grid>
        <Rectangle x:Name="TitleBox" Fill="#FFECDC54">
          <Rectangle.Stroke>
            <LinearGradientBrush EndPoint="0.5,1" StartPoint="0.5,0">
              <LinearGradientBrush.RelativeTransform>
                <TransformGroup>
                  <ScaleTransform CenterY="0.5" CenterX="0.5"/>
                  <SkewTransform CenterY="0.5" CenterX="0.5"/>
                  <RotateTransform Angle="140" CenterY="0.5" CenterX="0.5"/>
                  <TranslateTransform/>
                </TransformGroup>
              </LinearGradientBrush.RelativeTransform>
              <GradientStop Color="#FFA09F9F" Offset="0.4"/>
              <GradientStop Color="White" Offset="0.5"/>
            </LinearGradientBrush>
          </Rectangle.Stroke>
        </Rectangle>
        <ContentPresenter HorizontalAlignment="Left" RecognizesAccessKey="True" 
                          SnapsToDevicePixels="{TemplateBinding SnapsToDevicePixels}">
          <ContentPresenter.Resources>
              <Style TargetType="{x:Type TextBlock}">
                <Setter Property="TextWrapping" Value="NoWrap"/>
                <Setter Property="TextTrimming" Value="None"/>
                <Setter Property="FontSize" Value="32"/>
                <Setter Property="FontFamily" Value="Franklin Gothic Medium Cond"/>
              </Style>
          </ContentPresenter.Resources>
        </ContentPresenter>
      </Grid>
    </ControlTemplate>
  </Label.Template>
</Label>

This will apply your style to the generated TextBlock element.