no se si es esto lo que quieres pero en esta parte de código le agregaría lo siguiente
<html>
<head>
<title>Consulta</title>
</head>
<body>
<p>
<?php
$conexion = mysql_connect("localhost", "root", "") or die("Problemas en la conexion");
mysql_select_db("empresa", $conexion) or die("Problemas en la selección de la base de datos");
$registros = mysql_query("select cedula,apellidos,nombre,puesto, sueldo from personal where cedula='$_REQUEST[cedula]'", $conexion) or die("Problemas en el select:" .mysql_error());
$reg = mysql_fetch_array($registros
if (reg['cedula']<>"") {
echo "Cedula:" . $reg['cedula'] . "<br>";
echo "Apellidos:" . $reg['apellidos'] . "<br>";
echo "Nombres:" . $reg['nombre'] . "<br>";
echo "Puesto" . $reg['puesto'] . "<br>";
echo "Sueldo" . $reg['sueldo'] . "<br>";
?>
<br> <a href="formeditar.php?cedulaA=<?=$_REQUEST['cedula']?>"> Editar</a>
<br> <a href="eliminar.php?cedula=<?=$_REQUEST['cedula']?>" onClick="if(!confirm('Realmente desea eliminar el registro?')) return false"> Eliminar</a>
<?php
} else {
echo "Cedula No registrada .";
}
mysql_close($conexion);
?>
</body>
</html>
así si se realiza la consulta y no existe te dice que no se encuentra, si si encuentra te muestra los datos
espero te sirva y sea lo que querias