Hi @becky,
Its batter if you create same menu for different sites, because it will not create any issue when you have different themes on your WP Multi Sites.
If you have same theme then easily we can do this, but As described If you have different themes you can use each site client to make same header changes.
If you have any further questions feel free to ask.
Thanks
