Thought i'd just add the code to make it a bit clearer...

Page:

apex:page controller="RentalEvidenceSearchController" sidebar="false">
 
  <apex:form >
  <apex:pageMessages id="errors" />
 
  <apex:pageBlock title="Find Evidence!" mode="edit">
 
  <table width="100%" border="0">
  <tr>  
    <td width="200" valign="top">
 
      <apex:pageBlock title="Parameters" mode="edit" id="criteria">
 
      <script type="text/javascript">
      function doSearch() {
      
        searchServer(
          document.getElementById("operator").value,
          document.getElementById("address").value,
          document.getElementById("postcode").value,
          document.getElementById("trans").options[document.getElementById("trans").selectedIndex].value
          );
          
      }
      </script> 
 
      <apex:actionFunction name="searchServer" action="{!runSearch}" rerender="results,debug,errors">
          <apex:param name="operator" value="" />
          <apex:param name="address" value="" />
          <apex:param name="postcode" value="" />
          <apex:param name="transactions" value="" />
      </apex:actionFunction>
 
      <table cellpadding="2" cellspacing="2">
      <tr>
        <td style="font-weight:bold;">Operator<br/>
        <input type="text" id="operator" onkeyup="doSearch();"/>
        </td>
      </tr>
      <tr>
        <td style="font-weight:bold;">Address<br/>
        <input type="text" id="address" onkeyup="doSearch();"/>
        </td>
      </tr>
      <tr>
        <td style="font-weight:bold;">Postcode<br/>
        <input type="text" id="postcode" onkeyup="doSearch();"/>
        </td>
      </tr>
      <tr>
        <td style="font-weight:bold;">Transaction<br/>
          <select id="transaction" onchange="doSearch();">
            <option value=""></option>
            <apex:repeat value="{!transactions}" var="tran">
              <option value="{!tran}">{!tran}</option>
            </apex:repeat>
          </select>
        </td>
      </tr>
     
      
      </table>
 
      </apex:pageBlock>
 
    </td>
    <td valign="top">
 
    <apex:pageBlock mode="edit" id="results">
 
        <apex:pageBlockTable value="{!rents}" var="Rent">
 
            <apex:column >
                <apex:facet name="header">
                    <apex:commandLink value="Operator" action="{!toggleSort}" rerender="results,debug">
                        <apex:param name="sortField" value="operator" assignTo="{!sortField}"/>
                    </apex:commandLink>
                </apex:facet>
                
  <!--               <apex:outputlink value="/{!Rent.id}">        -->
                     <apex:outputlink value="/apex/RentalEvidence?id={!Rent.Id}">
                   <apex:outputField value="{!Rent.Operator__c}"/>
                </apex:outputlink>
                
                
      <!--          <apex:outputField value="{!Rent.Operator__c}"/> -->
            </apex:column>
 
            <apex:column >
                <apex:facet name="header">
                    <apex:commandLink value="Address" action="{!toggleSort}" rerender="results,debug">
                        <apex:param name="sortField" value="address" assignTo="{!sortField}"/>
                    </apex:commandLink>
                </apex:facet>
            <!--     apex/RentalEvidence? -->
                <apex:outputField value="{!Rent.Address__c}"/>
            </apex:column>
 
            <apex:column >
                <apex:facet name="header">
                    <apex:commandLink value="Postcode" action="{!toggleSort}" rerender="results,debug">
                        <apex:param name="sortField" value="postcode" assignTo="{!sortField}"/>
                    </apex:commandLink>
                </apex:facet>
                <apex:outputField value="{!Rent.Postcode__c}"/>
            </apex:column>
 
            <apex:column >
                <apex:facet name="header">
                    <apex:commandLink value="Transaction" action="{!toggleSort}" rerender="results,debug">
                        <apex:param name="sortField" value="interested_technologies__c" assignTo="{!sortField}"/>
                    </apex:commandLink>
                </apex:facet>
                <apex:outputField value="{!Rent.Transaction__c}"/>
            </apex:column>
 
        </apex:pageBlockTable>
 
    </apex:pageBlock>
 
    </td>
  </tr>
  </table>
 
  <apex:pageBlock title="Debug - SOQL" id="debug">
      <apex:outputText value="{!debugSoql}" />           
  </apex:pageBlock>    
 
  </apex:pageBlock>
 
  </apex:form>
 
</apex:page>

Controller:

public with sharing class RentalEvidenceSearchController {
 
  // the soql without the order and limit
  private String soql {get;set;}
  // the collection of contacts to display
  public List<Rental_Evidence__c> rents {get;set;}
 
  // the current sort direction. defaults to asc
  public String sortDir {
    get  { if (sortDir == null) {  sortDir = 'asc'; } return sortDir;  }
    set;
  }
 
  // the current field to sort by. defaults to last name
  public String sortField {
    get  { if (sortField == null) {sortField = 'Operator__c'; } return sortField;  }
    set;
  }
 
  // format the soql for display on the visualforce page
  public String debugSoql {
    get { return soql + ' order by ' + sortField + ' ' + sortDir + ' limit 20'; }
    set;
  }
 
  // init the controller and display some sample data when the page loads
  public RentalEvidenceSearchController() {
    soql = 'select ID, Operator__c, Address__c, Postcode__c, Transaction__c from Rental_Evidence__c';
    runQuery();
  }
 
  // toggles the sorting of query from asc<-->desc
  public void toggleSort() {
    // simply toggle the direction
    sortDir = sortDir.equals('asc') ? 'desc' : 'asc';
    // run the query again
    runQuery();
  }
 
  // runs the actual query
  public void runQuery() {
 
    try {
      rents = Database.query(soql + ' order by ' + sortField + ' ' + sortDir + ' limit 20');
    } catch (Exception e) {
        //ApexPages.Message myMsg = new ApexPages.Message(ApexPages.severity, summary, detail);
       //String summary = e.getSummary();
      ApexPages.addMessage(new ApexPages.Message(ApexPages.Severity.ERROR,''));
    }
 
  }
 
  // runs the search with parameters passed via Javascript
  public PageReference runSearch() {
     
    String operator = Apexpages.currentPage().getParameters().get('operator');
    String address = Apexpages.currentPage().getParameters().get('Address__c');
    String postcode = Apexpages.currentPage().getParameters().get('Postcode__c');
    String trans = Apexpages.currentPage().getParameters().get('Transaction__c');
 
    soql = 'select Operator__c, Address__c, Postcode__c, Transaction__c from Rental_Evidence__c where Operator__c != null';
    if (!operator.equals(''))
      soql += ' and Operator__c LIKE \''+String.escapeSingleQuotes(operator)+'%\'';
    if (!address.equals(''))
      soql += ' and Address__c LIKE \''+String.escapeSingleQuotes(address)+'%\'';
    if (!postcode.equals(''))
      soql += ' and Postcode__c LIKE \''+String.escapeSingleQuotes(postcode)+'%\'';  
    if (!trans.equals(''))
      soql += ' and Transaction__c includes (\''+trans+'\')';
 
    // run the query again
    runQuery();
 
    return null;
  }
 
  // use apex describe to build the picklist values
  public List<String> transactions {
    get {
      if (transactions == null) {
 
        transactions = new List<String>();
        Schema.DescribeFieldResult field = Rental_evidence__c.Transaction__c.getDescribe();
 
        for (Schema.PicklistEntry f : field.getPicklistValues())
          transactions.add(f.getLabel());
 
      }
      return transactions;          
    }
    set;
  }
 
}

Thanks

Paul