Non entro nel merito di scrivere nella parte destra di tutte le testatine sempre e soltanto il “Capitolo
L’aspetto tecnico di ciò che tu chiedi è questo: se unsi book o simili, subito dopo \begin{document} metti \frontmatter} e prima del primo capitolo da numerare metti \mainmatter; alla fine dopo l’ultimo capitolo numerato metti \beckmatter che conterrà presumibilmente solo la bibliografia, ma potrebbe contenere alcune delle appendici (non numerate) uno o più indici analitici, glossari, lista di acronimi e simili.
Oppure visto che certamente non usi quei comandi ma usi \chapter*{Introduzione}, scrivici dopo \markboth{Introduzione}{Introduzione};
Oppure specifica di voler usare lo stile plain da subito dopo \begin{document} e poi specifichi lo stile fancy subito prima del primo capitolo da numerare.
Oppure…
Puoi sbizzarrirti a trovare altre soluzioni (una delle quali implica di non usare lo stile fancy e usare gli stili predefiniti, ma se è questo che vuoi…)