Lo más sencillo es construir dinámicamente la consulta:
Código PHP:
$where = "";
$provincia=$_POST['provincia'];
if($provincia!="Todas las provincias")
{$provincia= "WHERE provincia = '".$provincia."'";}
$result = mysql_query("SELECT * FROM propiedades ".$where);
SI la variable es diferente "Todas las provincias", le pone la cadena del WHERE a la variable, de lo contrario sólo contendrá una cadena vacía que no afectará el resto de la consulta.
Quiero que conste que este no es tema de MySQL sino de programación en PHP, y deberías haberlo posteado en otro foro (Foro de PHP).