<apex:page controller="searchcls" >
  <apex:form >
  <apex:pageBlock >
      
  <apex:inputText value="{!stringval}"/>
  <apex:commandButton value="search" action="{!search}" reRender="account"/><!--I added a rerender attribute so that the page would stop trying to refresh instead it just refreshes the pageblock below-->
  </apex:pageBlock>
     
  <apex:pageBlock id="account"><!--I added an id so that the command button knew what to refresh-->
      <h1 style='color:blue'>
          {!message}<!--This is where the page message will display-->
      </h1>
      
  <apex:pageblockTable value="{!acctlst}" var="a">
  <apex:column headerValue="Account Name" value="{!a.name}"/>
  <apex:column headerValue="Fax" value="{!a.Fax}"/>
  <apex:column headerValue="Phone" value="{!a.phone}"/>
  <apex:column headerValue="Billingcountry" value="{!a.billingcountry}"/>
  <apex:column headerValue="Billingstate" value="{!a.billingstate}"/>
  </apex:pageblockTable>
  </apex:pageBlock>
  </apex:form>
     
</apex:page>

public class searchcls {
    public List<Account> acctlst { get; set; }
    public String stringval { get; set; }
    public String message {get;set;}//This is what will be used to display our message
    //I changed your method from a return type to a void that way your page is not trying to redirect
    public void search() {
       acctlst = (List<Account>)[FIND: stringval RETURNING Account(name, fax, phone, billingstate, billingcountry)][0];       
         if(acctlst.size() > 0)//You had the the ! on the wrong side
         {
             //Since I am not trying to return anything Im using our message to let the user know if their search is successful or not.
             message = 'Is this the Account you were looking for?';
             
             
         } else {
        
            //Since I am not trying to return anything Im using our message to let the user know if their search is successful or not.
           
            message = 'No Accounts';
        }
   }
}