As you want the variable to be defined as well in your terminal shells (interactive non-login shell) and for the desktop launcher icons (X-server started by non-interactive login shell) you should put the definition in your ~/.zshenv.
And yes, you have to restart your x-session in order to have the new environment available for your desktop icons. Imagine such a startup scheme: Graphical Login -> Use your default shell to start the X session -> Desktop -> Shell terminal / Launch program via icon, so the child shells inherit the environment from the parent, which is used to start the X session. That shell read the RC-files only once -- on your login to the X session.
For the bonus point. This is what the manual says:
export [ name[=value] ... ]The specified names are marked for automatic export to the environment of subsequently executed commands. (...)
If you define your variable in ~/.zshenv, you can in principle omit the export as this file is read in by default. The only difference arises if you start a shell with zsh -f, which sources no RC files. A little demonstration:
% foo=foo_defined % export bar=bar_defined % print -l $foo $bar foo_defined bar_defined % zsh -f % print -l $foo $bar bar_defined % I. e. only the exported $bar is defined in subsequent shells. But to be on the safe side, use export -- I can't think of a case where this is harmful.