In realtà anche virus ti diceva la stessa cosa (2 submit a script php salva dati in sessione 3 redirect a pagina.html ).
Comunque per gli header basta che metti all'inizio inizio, prima di qualsiasi codice:
ob_start;
e alla fine
ob_end_flush;.
Per il salvataggio dati, li devi mandare da qualche parte! Quindi ti serve una pagina che riceva i dati, li salvi e ti rinvii alla pagina con il form.
E' così che funziona.
Se vuoi rimanere nella stessa pagina, ti fai una condizione per la quale, se ricevi dati da $_POST, allora salvi i nuovi dati nel db, ma così facendo ti carica gli stessi dati.
Dovresti fare un refresh per ottenere i nuovi dati.
E' un bordello. Fattibile ma con una specie di "doppio refresh" stilisticamente brutto.
Ti fai una pagina semplice con il recupero delle variabili

$nome=$_POST['nome'];
$cognome=$_POST['cognome'];
mysql_query("UPDATE tabella SET nome='$nome', cognome='$cognome' WHERE id=$_COOKIE['id'] ")
header("location:form.php?a=z");

In questo modo ho ipotizzato che l'id utente era salvato in un cookie.
Ho anche assegnato i valori post a variabili ma potevi inserire direttamente il $_POST nella query, saltando quel passaggio.
Alla fine rimandi alla pagina con il form.
la variabile $_GET['a'] è simbolica. E' come dire: guarda che arrivo da quella pagina!!
Puoi mettere anche: se la pagina precedente era salva.php, allora visualizza un alert.
Dipende da quello che vuoi fare e la facilità col la quale farlo.