Si el menú contextual está "codificado" en xaml, entonces es fácil agregar submenús. Por ejemplo:

<ContextMenu>
    <MenuItem Header="Comm1" Command="{Binding Blabla1}">
        <MenuItem Header="SubComm1" Command="{Binding Blabla2}"></MenuItem>
    </MenuItem>
    <MenuItem Command="Comm2"></MenuItem>
    <MenuItem Command="Comm3"></MenuItem>
</ContextMenu>

Esto significa que ContextMenu tiene tres elementos (Comm1, Comm2 y Comm3) y Comm1 tiene submenú SubComm1.

He hecho mi ContextMenu un poco más flexible:

<ContextMenu ItemsSource="{Binding ContextMenuItemsSource}">
    <ContextMenu.ItemContainerStyle>
        <Style TargetType="MenuItem">
            <Setter Property="Header" Value="{Binding ContextMenuCommandHeader}"></Setter>
            <Setter Property="Command" Value="{Binding ContextMenuCommand}"></Setter>
        </Style>
     </ContextMenu.ItemContainerStyle>
</ContextMenu>

Básicamente puedo tener cualquier número de elementos en ContextMenu, y cualquier elemento puede tener cualquier Comando. ¿Cómo puedo agregar un submenú al elemento ContextMenu?