Saludos..
Prueba primero que las variables si se estan enviando por POST o que el nombre de las variables correspondan a los name de los campos input donde estas guardando la informacion.
Código PHP:
//Datos de conexión a la base
$link= mysql_connect("localhost", "root","123456");
mysql_select_db("libreria",$link);
$nombre=$_POST["nombre"];
$direccion=$_POST["direccion"];
$ciudad=$_POST["ciudad"];
$sql="INSERT INTO Clientes (Nombre,Direccion,Ciudad) values('$nombre','$direccion','$ciudad')";
echo $sql;
mysql_query($sql,$link)or die(mysql_error());
Ya de esto modo te podras dar cuanta que puede estar pasando...
Hasta Pronto!