Ya está solucionado, JOIN nunca falla!
Código PHP:
$tabla = mysql_query("SELECT * FROM coches INNER JOIN ciudades ON coches.idciudad = ciudades.idciudad INNER JOIN marcas ON coches.idmarca = marcas.idmarca INNER JOIN modelos ON coches.idmodelo = modelos.idmodelo WHERE coches.idmarca = '6'" . $criterio . " limit " . $inicio . "," . $TAMANO_PAGINA);