Verficare se il valore fornito dall'utente esiste nel database

[boots]

Prima di tutto, visto che sei agli inizi, lascia perdere le istruzioni mysql_* che sono deprecate. Passa a PDO (o Mysqli).

Tornando al tuo quesito, il fatto è che se lasci vuoto il campo, la tua condizione sql diventa

$sql="SELECT * FROM telefoni WHERE marca LIKE '%%'";

che in pratica è come se non ci fosse (ti vengono ritrovati tutti i record).

Quello che dovresti fare è verificare se $marca non sia vuoto e in caso contrario mostrare il messaggio.
Esempio:

$marca=$_POST['marca'];

if($marca){
  // Si fa l'escape della stringa per evitare problemi con i caratteri speciali e come precauzione per sql injection
  $marca = mysql_real_escape_string($marca);
  $sql="SELECT * FROM telefoni WHERE marca LIKE '%$marca%'";
  $rs = @mysql_query("$sql",$link) or die("Errore query database: " . mysql_error());
  ...
  ...
}else{
  echo "Inserisci la marca del cellulare".
}