What does `zstyle` do?

zstyle handles the obvious style control for the completion system, but it seems to cover more than just that. E.g., the vcs_info module relies on it for display of git status in your prompt. You can start by looking at the few explanatory paragraphs in man zshmodules in the zstyle section.

You can simply invoke it to see what settings are in effect. This can be instructive.

The Zsh Book has a nice chapter treatment on zstyle, also, explaining in detail its various fields.

You could grep around in the .../Completion/ directory on your system to see how some of those files make use of zstyle. A common location is near /usr/share/zsh/functions/Completion/*. I see it used in 100+ files on my system there. Users often have zstyle sprinkled around their ~/.zshrc, too. Here are some nice ones to add some color and descriptions to your completing:

# Do menu-driven completion.
zstyle ':completion:*' menu select

# Color completion for some things.
# http://linuxshellaccount.blogspot.com/2008/12/color-completion-using-zsh-modules-on.html
zstyle ':completion:*' list-colors ${(s.:.)LS_COLORS}

# formatting and messages
# http://www.masterzen.fr/2009/04/19/in-love-with-zsh-part-one/
zstyle ':completion:*' verbose yes
zstyle ':completion:*:descriptions' format "$fg[yellow]%B--- %d%b"
zstyle ':completion:*:messages' format '%d'
zstyle ':completion:*:warnings' format "$fg[red]No matches for:$reset_color %d"
zstyle ':completion:*:corrections' format '%B%d (errors: %e)%b'
zstyle ':completion:*' group-name ''

# Completers for my own scripts
zstyle ':completion:*:*:sstrans*:*' file-patterns '*.(lst|clst)'
zstyle ':completion:*:*:ssnorm*:*' file-patterns '*.tsv'
# ...

The completion system makes most of the fields clear if you play around with it. Try typing zstyle :«tab» and you see some options. Tab-complete to the next colon and you’ll see the next set of options, etc.

To properly understand how zstyle works, you first need to understand that zsh is a modular program. From man zshmodules

Some optional parts of zsh are in modules, separate from the core of the shell. Each of these modules may be linked in to the shell at build time, or can be dynamically linked while the shell is running if the installation supports this feature. [...]

In this regard zsh is more like an interpreter like PHP where the main builtin commands are defined in the "core" module, but other builtin commands are contained in "modules".
Ok great, so then what is "zstyle"?
zsh, like other shells has builtin commands, such as source, cd or declare - zstyle is a just another one of these "builtins".

Scope of builtins and shell options

builtins and shell options are usually "global" in the sense that they are generally (but not always) applicable/usable at any time or context throughout the shell process, or in other words, they generally apply to zsh and all the sub-systems (modules). Note this applies whether a shell is invoked as an interactive or non-interactive interpreter.
So, for example you can use the builtin's source or cd or the shell option "globstar" will be valid whether at a command prompt or in a case statement in a non-interactive script or in a function in that same script.
Contrary to another answer above, zstyle is not a builtin that is specific to the "compsys" (completions system) module, zstyle is a "global" builtin.

zstyle is defined by the zsh/util module, this simply means that the code which defines how to parse, and "do" zstyle is defined in the zsh/zutil module.
You could just as well forget this fact, i.e. bash doesn't require you to know that the code for the eval builtin is contained in the file eval.c, but to get help for zstyle, it helps to know that zstyle is a builtin defined in the zsh/zutil module, and the documentation for the zsh/zutil module can be accessed by runningman zshmodules.

Setting options that are specific to a module or a shell function

So traditionally shell options have generally been "global", but as per the description from man zshmodules, Some optional parts of zsh are in modules, and also, a lot of the zsh functionality has been written in shell functions. (similar to how a lot of core and optional functionality of vim has been written in vimscript).
So then if you want to be able to specify options that apply just to these modules or functions, how would you do it?
Well that's what zstyle does, give you the ability to "target" options at a much finer level than traditional "global" shell options.
zstyle achieves this through the argument "pattern"

An example command which configures some optional behavior specific to "compsys":

zstyle ':completion::complete:lsof:*' menu yes select

and configuring some optional behavior specific to "vcs_info":

zstyle ':vcs_info:*' actionformats \
      '%F{5}(%f%s%F{5})%F{3}-%F{5}[%F{2}%b%F{3}|%F{1}%a%F{5}]%f '

But it doesn't stop there, zstyles ability to target contexts is incredibly powerful, for example, say you wanted to define some behaviour/options for the vcs_info feature, when you were is a .git repository, as opposed to a svn repo, then you could modify the context pattern

:vcs_info:<svn_or_whatever_SCM_system>:* <style>

What about optional behaviour for a specific project, with a svn repo? then

:vcs_info:<svn_or_whatever_SCM_system>:*:repo-root-name <style>

The only vaguely meaningful description of the stupidly named, and ill-documented "(z)style" I've found - comes from the glossary of From Bash To The Z Shell

style

In zsh, the style mechanism is a flexible way of configuring shell add- ons that use functions, such as the completion system and editor widgets. Unlike variables they can be different in different contexts and unlike shell options they can take values. The mechanism is based on the command style.

also, in the section "Handling Styles", the author further elaborates...

With more sophisticated completion functions, you may want to allow aspects of the function’s behavior to be configurable using style.

... many helper functions look up styles for you so your function will react to many styles without your function having to do anything in particular. To get an idea of the styles looked up in a particular situation, invoke the _complete_help function with a numeric argument. Normally, you can do this by pressing Esc2 followed by Ctrl-x h. This is primarily useful when configuring completion because it allows you to see what styles are looked up and the associated context.