Note that this answer is outdated and Sergey Romanovsky gives a much better one. I cannot delete this one because it is marked accepted, but please note it now serves more as a basic illustration of zsh's widget programming.

Custom widget history-incremental-multi-search for zsh

Setup

Create a directory and include it in your $fpath For example, I created a directory ~/.zsh/functions, and the line fpath=($HOME/.zsh/functions $fpath) in my .zshrc.

Put the following in a file named history-incremental-multi-search in that directory.

emulate -L zsh
setopt extended_glob

local oldbuffer=$BUFFER
local -i oldcursor=$CURSOR

local dir                # search direction
local chars              # input buffer
local -a words           # search terms
local -a found           # all history items that match first term
local -i hindex=$HISTNO  # current 
local -i lmatch          # last matched history item (for prev/next)

if [[ $WIDGET == *forward* ]]; then
    dir=fwd
else
    dir=bck
fi

function find-next {
    # split the input buffer on spaces to get search terms
    words=(${(s: :)chars})

    # if we have at least one search term
    if (( $#words )); then
        # get all keys of history items that match the first
        found=(${(k)history[(R)*$words[1]*]})
        if (( $#found )); then
            # search in widget direction by default
            # but accept exception in $1 for "prev match"
            search-${1:-$dir}
        else
            # no matches
            lmatch=$HISTNO
        fi
    else
        # no search terms
        lmatch=$HISTNO
        BUFFER=$oldbuffer
        CURSOR=$oldcursor
    fi
}

function search-fwd {
    # search forward through matches
    local -i i
    for (( i = $#found; i > 0; i-- )); do
        # but not before hindex as we're searching forward
        if [[ $found[$i] -gt $hindex ]]; then
            set-match $found[$i]
        fi
    done
}

function search-bck {
    # search backward through matches
    local -i i
    for (( i = 1; i <= $#found; i++ )); do
        # but not beyond hindex as we're searching backward
        if [[ $found[$i] -lt $hindex ]]; then
            set-match $found[$i]
        fi
    done
}

function set-match {
    # match history item against all terms and select it if successful
    local match=1
    local -i i
    for (( i = 2; i <= $#words; i++ )); do
        if [[ $history[$1] != *$words[$i]* ]]; then
            match=0
            break
        fi
    done
    if [[ $match -ne 0 ]]; then
        lmatch=$1
        BUFFER=$history[$1]
        CURSOR=$#BUFFER
        break
    fi
}

# display sub prompt
zle -R "${dir}-i-search-multi:"

# handle input keys
while read -k; do
    case $REPLY in
        # next
        $'\C-n' )
            hindex=$lmatch
            find-next
            ;;
        # prev
        $'\C-p' )
            hindex=$lmatch
            if [[ $dir == fwd ]]; then
                find-next bck
            else
                find-next fwd
            fi
            ;;
        # break
        $'\e' | $'\C-g' )
            BUFFER=$oldbuffer
            CURSOR=$oldcursor
            break
            ;;
        # accept
        $'\C-m' | $'\C-j' )
            if [[ $lmatch -eq $HISTNO ]]; then
                BUFFER=$oldbuffer
                CURSOR=$oldcursor
            else
                HISTNO=$lmatch
            fi
            break
            ;;
        # erase char
        $'\C-h' | $'\C-?' )
            chars=$chars[1,-2]
            hindex=$HISTNO
            find-next
            ;;
        # erase word
        $'\C-w' )
            if [[ $chars =~ \  ]]; then
                chars=${chars% *}
            else
                chars=
            fi
            hindex=$HISTNO
            find-next
            ;;
        # kill line
        $'\C-u' )
            chars=
            hindex=$HISTNO
            find-next
            ;;
        # add unhandled chars to buffer
        * )
            chars=${chars}${REPLY}
            hindex=$HISTNO
            find-next
            ;;
    esac

    zle -R "${dir}-i-search-multi: $words"
done

Put this in or source it from your .zshrc:

autoload -U history-incremental-multi-search

# make new widgets from function
zle -N history-incremental-multi-search-backward history-incremental-multi-search
zle -N history-incremental-multi-search-forward history-incremental-multi-search

# bind the widgets to keys
bindkey '^Xr' history-incremental-multi-search-backward
bindkey '^Xs' history-incremental-multi-search-forward

Use

You should now be able to initiate a backward incremental search with Ctrl+X, r, forward with Ctrl+X, s.

Type your search terms separated by space. Following keys are available to control it:

• ← Backspace: erase character

• Ctrl+W: erase word

• Ctrl+U: kill line

• Ctrl+N: next match

• Ctrl+P: previous match

• Ctrl+G/Esc: cancel search

• Enter: accept

This solution can probably be simplified quite a bit. It's more a functional proof of concept, with lots of room for improvement.

Of course you can no longer use Ctrl+R. If you consult the Z Shell manual you'll see that there's only a key binding for the history-incremental-search-backward widget in the emacs keymap. There are no key bindings for it in the vi keymaps.

But as you'll also find from reading the manual (It's chapter 18.), adding a key binding is a fairly simple exercise in the use of the bindkey command:

bindkey "^R" history-incremental-search-backward

You don't even have to use the zle command to map the widget onto a shell function, since this is a standard widget.

If you consult the answer to this same question that is on the Z Shell wiki, you'll see the commands for specifically adding this to the vi "command" and "insert mode" keymaps:

bindkey -M viins '^R' history-incremental-search-backward
bindkey -M vicmd '^R' history-incremental-search-backward

Also note that, as garyjohn points out, in the vi "command" keymap, the / character is bound to the vi-history-search-backward widget. The difference between this widget and the history-incremental-search-backward widget is the widget behaviour that applies once one is in history search mode. Here are a couple of the differences that you will notice:

• Switching vi modes:
  • The search mode in history-incremental-search-backward toggles between the main and vicmd keymaps when you invoke the vi-cmd-mode widget whilst still staying in search mode. i.e. from emacs mode presssing the Esc key or Ctrl+XCtrl+V keys toggles the search mode between the emacs and vicmd keymaps. (Invoking history-incremental-search-backward from the vicmd keymap is thus troublesome, unless you bind something to vi-cmd-mode in the vicmd keymap as well.)
  • The search mode in vi-history-search-backward treats the vi-cmd-mode widget as accept-line and will end the search, re-entering the command mode that you entered the search from. i.e. (with the default bindings) / enters search mode from command mode and Esc goes back to command mode.
• Repeating a search:
  • In history-incremental-search-backward, both the history-incremental-search-backward and the vi-rev-repeat-search widgets are recognized. i.e. (presuming that you have altered the bindings as above) both Ctrl+R and N will search for a preceding matching line.
  • In vi-history-search-backward, only the vi-rev-repeat-search widget is recognized. i.e. (presuming that you have altered the bindings as above) Ctrl+R will cause a beep and be ignored.