What does "export" do in shell programming?

Exported variables such as $HOME and $PATH are available to (inherited by) other programs run by the shell that exports them (and the programs run by those other programs, and so on) as environment variables. Regular (non-exported) variables are not available to other programs.

$ env | grep '^variable='
$                                 # No environment variable called variable
$ variable=Hello                  # Create local (non-exported) variable with value
$ env | grep '^variable='
$                                 # Still no environment variable called variable
$ export variable                 # Mark variable for export to child processes
$ env | grep '^variable='
variable=Hello
$
$ export other_variable=Goodbye   # create and initialize exported variable
$ env | grep '^other_variable='
other_variable=Goodbye
$

For more information, see the entry for the export builtin in the GNU Bash manual, and also the sections on command execution environment and environment.

Note that non-exported variables will be available to subshells run via ( ... ) and similar notations because those subshells are direct clones of the main shell:

$ othervar=present
$ (echo $othervar; echo $variable; variable=elephant; echo $variable)
present
Hello
elephant
$ echo $variable
Hello
$

The subshell can change its own copy of any variable, exported or not, and may affect the values seen by the processes it runs, but the subshell's changes cannot affect the variable in the parent shell, of course.

Some information about subshells can be found under command grouping and command execution environment in the Bash manual.

Well, it generally depends on the shell. For bash, it marks the variable as "exportable" meaning that it will show up in the environment for any child processes you run.

Non-exported variables are only visible from the current process (the shell).

From the bash man page:

export [-fn] [name[=word]] ...
export -p

The supplied names are marked for automatic export to the environment of subsequently executed commands.

If the -f option is given, the names refer to functions. If no names are given, or if the -p option is supplied, a list of all names that are exported in this shell is printed.

The -n option causes the export property to be removed from each name.

If a variable name is followed by =word, the value of the variable is set to word.

export returns an exit status of 0 unless an invalid option is encountered, one of the names is not a valid shell variable name, or -f is supplied with a name that is not a function.

You can also set variables as exportable with the typeset command and automatically mark all future variable creations or modifications as such, with set -a.

it makes the assignment visible to subprocesses.

$ foo=bar
$ bash -c 'echo $foo'

$ export foo
$ bash -c 'echo $foo'
bar