seria una cosa asi:
Código PHP:
$cedula = trim($_POST['cedula']);
$sql_chk = mysql_query("SELECT * FROM clientes WHERE cedula='$cedula'",$linkbd) or die(mysql_error());
$row =mysql_num_rows($sql_chk);
if($row ==0){
echo "la cedula ya existe";
//tambien puedes poner un boton de voler al form con js
} else {
header("Location: pagina.php"); //o en vez de redirigir, cierras el IF, quitas el ELSE y continuas procesando los datos
}