fish doesn't implement incremental history search, although it seems to come up fromtime to time. The pre-2.0 documentation has a "Missing features and bugs" section 1 which lists incremental history search fairly far down in the "Possible features" list. The fish-users mailing list includes this message from Axel Liljencratz, dated August 21, 2006, in which he says that incremental search would be a nice feature to have.
If you're used to bash-style incremental search, fish history searching does take a bit of getting used to. You have to type the search term first, and you move up and down matching entries with up- and down- arrow. But I suppose you get used to it.