Insertar registro

Puedes usar algo así:
header("location: tu_archivo.php");
Debes de considerar que esto redireccionará automáticamente a la página que tu quieras (dándole el correcto path). Además no debes de enviar nada antes al navegador del cliente.
Modo incorrecto
<?php
$insert = "INSERT INTO...";
$q = mysql_db_query($dbname,$q) or die($insert."<br>".mysql_error());
echo "Datos ingresados correctamente"; //esto es lo q no puedes hacer
header("location: tu_archivo.php");
?>
Modo correcto
<?php
$insert = "INSERT INTO...";
$q = mysql_db_query($dbname,$q) or die($insert."<br>".mysql_error());
header("location: tu_archivo.php");
?>
Puedes pasarles algunas variables para verificar el resultado
header("location: tu_archivo.php?verificar=true");
Deberías de considerar hacer todo en una misma página, es más práctico y te permite eso, ir directamente a la misma.
<?php
if(!isset($enviar)){//si $enviar no esta definida mostramos el formulario
?>
<form action="<?=$_SERVER['PHP_SELF'];?>" method="POST">
NOMBRE: <input type="text" name="nombre">
APELLIDO: <input type="text" name="apellido">
<input type="submit" name="enviar" value="Enviar formulario">
<?php
}else{
$nombre = $_POST['nombre'];
$apellido = $_POST['apellido'];
$insert = "INSERT INTO tu_tabla (id, nombre, apellido) VALUES ('', '$nombre', '$apellido')";
$q = mysql_db_query($dbname,$q) or die($insert."<br>".mysql_error());
echo "Los datos fueron ingresados correctamente<br>";
echo "NOMBRE: ".$nombre."<br>";
echo "APELLIDO: ".$apellido."<br>";
}
?>
El isset($enviar) chequea que no se haya presionado el botón "enviar formulario", si no se ha presionado muestra el formulario, si sea ha presionado, recogemos los datos con $_POST, los introducimos a la DB y mostramos el mensaje de que los datos han sido introducidos correctamente y le mostramos los mismos.

Dentro del form agrega un campo oculto de nombre Acción y valor "agregar". Luego el destino del form lo pones en: "?" tal cual sin comillas. Al comienzo de la página 1 pones:
<? (if $Accion=="agregar"){
$q="insert into.....";
$res=mysql_query($q);
if ($err=mysql_error()){
$msg="ha ocurido el siguiente error: $err";
} else { $msg="se ha agregado correctamente";} ?>
Luego en donde quieras imprime el mensaje de resultado. Esta es la mejor opción y la más profesional. Otra es usando redireccionamiento con php o con javascript. Espera haberte sido útil, no olvides cerrar y valorar esta respuesta.