<select>変更を確認するには、値を実際の監視可能なプロパティにバインドする必要があります。
<-- ------------------------ here....................... -->
<select name="search_option" data-bind="value: criteria">
    <option value="O">Order Search</option>
    <option value="P">PO Number Search</option>
</select>
と
var orderSearchViewModel = {
   criteria: ko.observable("O")   // give a default value
};
orderSearchViewModel.helperText = ko.computed(function() {
    if (this.criteria() == "P") {
        return "Searching by PO Number";
    }else {
        return "Searching by Order Number";
    }
}, orderSearchViewModel);
ko.applyBindings(orderSearchViewModel);
criteriaこれは、基になる値を取得するために実行する必要がある関数であることに注意してください。
if (this.criteria == "P")
動作しません。
http://jsfiddle.net/dnfCb/11/
ところで、自己完結型のビューモデルの設定は少し良いと思います:
function OrderSearchViewModel() {
  var self = this;
  this.criteria = ko.observable("O");
  this.helperText = ko.computed(function() {
    if ( self.criteria() == "P" ) {
      return "Searching by PO Number";
    } else {
      return "Searching by Order Number";
    }
  });
}
ko.applyBindings( new OrderSearchViewModel() );