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.

This is often caused by commands in your history that are longer than 1 line. When you select a shorter item out of the history it doesn't seem to take into account the width of the prompt in re-rendering the command line, so everything after that long command is screwy.

The easy solution I've found is to hit the home key, insert "echo " and hit enter. Then recall the last command and edit from there. (First removing the echo. :)