In theories with spontaneous symmetry breaking, the phase transition can usually be characterized by a local order parameter $\Delta(x)$, which is not invariant under the relevant symmetry group $G$ of the Hamiltonian. The expectation value of this field has to be zero outside the ordered phase $\langle\Delta(x)\rangle = 0$, but non-zero in the phase $\langle\Delta(x)\rangle \neq 0$. This shows that there has been a spontaneous breaking of $G$ to a subgroup $H\subset G$ (where $H$ is the subgroup that leaves $\Delta(x)$ invariant).
What local means in this context, is usually that $\Delta(x)$ at point $x$, can be constructed by looking at a small neighborhood around the point $x$. Here $\Delta(x)$ can be dependent on $x$ and need not be homogeneous. This happens for example when you have topological defects, such as vortices or hedgehogs. One powerful feature of these Landau-type phases, is that there will generically be gapless excitations in the system corresponding to fluctuations of $\Delta(x)$ around its expectation value $\langle\Delta(x)\rangle$ in the direction where the symmetry is not broken (unless there is a Higgs mechanism). These are called Goldstone modes and their dynamics are described by a non-linear $\sigma$-model with target manifold $G/H$.
An example is the order parameter for s-wave superconductors $\langle\Delta(x)\rangle = \langle c_{\uparrow}(x)c_{\downarrow}(x)\rangle$, which breaks a $U(1)$ symmetry down to $\mathbb Z_2$. But there are no Goldstone modes due to the Higgs mechanism, the massive amplitude fluctuations are however there (the "Higgs boson"). [Edit: see EDIT2 for correction.]
A non-local order parameter does not depend on $x$ (which is local), but on something non-local. For example, a non-local (gauge-invariant) object in gauge theories are the Wilson loops
$W_R[\mathcal C] = \text{Tr}_R{\left(\mathcal Pe^{i\oint_{\mathcal C}A_\mu\text dx^\mu}\right)},$
where $\mathcal C$ is some closed curve. The Wilson loop thus depends on the whole loop $\mathcal C$ (and a representation $R$ of the gauge group) and cannot be constructed locally. It can also contain global information if $\mathcal C$ is a non-trivial cycle (non-contractible).
It is true that topological order cannot be described by a local order parameter, as in superconductors or magnets, but conversely a system described by a non-local order parameter does not mean it has topological order (I think). The above mentioned Wilson loops (and similar order parameters, such a the Polyakov and 't Hooft loop), is actually a order parameter in gauge theories which probe the spontaneous breaking of a certain center-symmetry. This characterizes the deconfinement/confinement transition of quarks in QCD: in the deconfined phase $W_R[\mathcal C]$ satisfies a perimeter law and quarks interact with a massive/Yukawa type potential $V(R)\sim \frac{e^{-mR}}R$, while in the confined phase it satisfy an area law and the potential is linear $V(R)\sim \sigma R$ ($\sigma$ is some string tension). There might be other examples of spontaneous symmetry breaking phases with non-local order parameter. [Edit: see EDIT2.]
Let me just make a few comments about topological order. In theories with with spontanous symmetry breaking, long-range correlations are very important. In topological order the systems are gapped by definition, and there is only short-range correlation. The main point is that in topological order, entanglement plays the important role not correlations. One can define the notion of long-range entanglement (LRE) and short-range entanglement (SRE). Given a state $\psi$ in the Hilbert space, loosely speaking $\psi$ is SRE if it can de deformed to a product state (zero entanglement entropy) by LOCALLY removing entanglement, if this is not possible then $\psi$ is LRE. A system which has a ground state with LRE is called topological order, otherwise its called the trivial phase. These phases have many characteristic features which are generally non-local/global in nature such as, anyonic excitations/non-zero entanglement entropy, low-energy TQFT's, and are characterized by so-called modular $S$ and $T$ matrices (projective representations of the modular group $SL(2,\mathbb Z)$).
Note that, unlike popular belief, topological insulators and superconductors are SRE and are NOT examples of topological order!
If one requires that the system must preserve some symmetry $G$, then not all SRE states can be deformed to the product state while respecting $G$. This means that SRE states can have non-trivial topological phases which are protected by the symmetry $G$. These are called symmetry protected topological states (SPT). Topological insulators/superconductors are a very small subset of SPT states, corresponding to restricting to free fermionic systems. Unlike systems with LRE and thus intrinsic topological order, SPT states are only protected as long as the symmetry is not broken. These systems typically have interesting boundary physics, such as gapless modes or gapped topological order on the boundary. Characterizing them usually requires global quantities too and cannot be done by local order parameters.
EDIT:
This is a response to the question in the comment section.
I am not sure whether there are any reference which discuss this point explicitly. But the point is that you can continuously deform/perturb the Hamiltonian of a topological insulator (while preserving the gap) into the trivial insulator by breaking the symmetry along the way (they are only protected if the symmetry is respected). This is equivalent to locally deforming the ground state into the product state, which is the definition of short range entanglement. You can find the statement in many papers and talks. See for example the first few slides here. Or even better, see this (slide with title "Compare topological order and topological insulator" + the final slide).
Let me make another comment regarding the distinction between intrinsic topological order and topological superconductors, which at first seems puzzling and contrary to what I just said. As was shown by Levin-Wen and Kitaev-Preskill, the entanglement entropy of ground state for a gapped system in 2+1D has the form
$S = \alpha A - \gamma + \mathcal O(\tfrac 1A)$,
where $A$ is the boundary area (this is called the area law, not the same area law I mentioned in the case of confinement), $\alpha$ is a non-universal number and $\gamma$ is universal and called the topological entanglement entropy (TEE). What was shown in the above papers is that the TEE is equal to $\gamma = \log\mathcal D$, where $\mathcal D\geq 1$ is the total quantum dimension and is only strictly $\mathcal D>1$ ($\gamma\neq 0$) if the system supports anyonic excitations.
Modulo some subtleties, LRE states always have $\gamma\neq 0$, which in turn means that they have anyonic excitations. Conversely for SRE states $\gamma = 0$ and there are no anyons present.
This seems to be at odds with the existence of 'Majorana fermions' (non-abelian anyons) in topological superconductors. The difference is that, in the case of topological order you have intrinsic finite-energy excitations which are anyonic and the anyons correspond to linear representations of the Braid group. While in the case of topological superconductors, you only have non-abelian anyons if there is an extrinsic defect (vortex, domain wall etc.) which the zero-modes can bind to, and they correspond to projective representation of the Braid group. The latter type anyons from extrinsic defects can also exist in topological order, but intrinsic finite-energy ones only exist in topological order. For more details, see the recent set of papers from Barkeshli, Jian and Qi.
EDIT2:
Please see my comments below for some corrections and subtleties. Such as, it is in a sense not correct that superconductors are described by a local order parameter. It only appears local in a particular gauge. Superconductors are actually examples of topological order, which is rather surprising.
Let me first answer your question "is it wrong to consider topological superconductors (such as certain p-wave superconductors) as SPT states? Aren't they actually SET states?"
(1) Topological superconductors, by definition, are free fermion states that have time-reversal symmetry but no U(1) symmetry (just like topological insulator always have time-reversal and U(1) symmetries by definition). Topological superconductor are not p+ip superconductors in 2+1D. But it can be p-wave superconductors in 1+1D.
(2) 1+1D topological superconductor is a SET state with a Majorana-zero-mode at the chain end. But time reversal symmetry is not important. Even if we break the time reversal symmetry, the Majorana-zero-mode still appear at chain end. In higher dimensions, topological superconductors have no topological order. So they cannot be SET states.
(3) In higher dimensions, topological superconductors are SPT states.
The terminology is very confusing in literature:
(1) Topological insulator has trivial topological order, while topological superconductors have topological order in 1+1D and no topological order in higher dimensions.
(2) 3+1D s-wave superconductors (or text-book s-wave superconductors which do not have dynamical U(1) gauge field) have no topological order, while 3+1D real-life s-wave superconductors with dynamical U(1) gauge field have a Z2 topological order. So 3+1D real-life topological superconductors (with dynamical U(1) gauge field and time reversal symmetry) are SET states.
(3) p+ip BCS superconductor in 2+1D (without dynamical U(1) gauge field) has a non-trivial topological order (ie LRE) as defined by local unitary (LU) transformations. Even nu=1 IQH state has a non-trivial topological order (LRE) as defined by LU transformations. Majorana chain is also LRE (ie topologically ordered). Kitaev does not use LU transformation to define LRE, which leads to different definition of LRE.
Best Answer
So many questions! First of all, it's a bit misleading to describe a Kitaev superconductor as spontaneously breaking $Z_2^f$. In fact, if you put a Kitaev superconductor on a system without boundary (i.e. periodic boundary conditions) there is no ground state degeneracy; the two-fold degenerate ground state for open boundary conditions really should be thought of a boundary modes.
The reason why people sometimes say this is that you can make a non-local transformation (Jordan-Wigner transformation) which relates the Kitaev superconductor to a quantum Ising chain, which does spontaneously break the $Z_2$ symmetry. But the order parameter for the quantum Ising chain doesn't map to anything local in the Kitaev superconductor. Therefore, from a conceptual point of view I think it's better to think of the Kitaev chain as entirely new topological phase and not try to understand it in terms of spontaneous symmetry breaking.
How do you see it's a topologically ordered state? Well, with open boundary conditions it has those topologically protected boundary modes. There is no local term you can add to the Hamiltonian that gaps out those boundary modes. This is not really related to any symmetry; it's just that that those two states are totally indistinguishable unless you look at the whole system so no local interaction could assign them different energies. It is possible to re-interpret this fact in terms of the non-local mapping to the quantum Ising model, but maybe a bit confusing.
To make connection with other definitions of topological order, this topologically protected degeneracy actually implies that you can't smoothly connect the Hamiltonian $H_K$ of the Kitaev superconductor to that of a trivial superconductor, $H_T$, without closing the bulk gap. To see this, we make use of a really useful mathematical trick called quasi-adiabatic continuation [1], which tells you that if $H_K$ and $H_T$ could be smoothly connected without closing the gap, there would exist a local unitary $\mathcal{U}$ relating the ground-state subspaces of $H_K$ and $H_T$. But $H_K$ has a two-fold degeneracy that cannot be closed by a local perturbation, whereas $H_T$ is trivial and therefore there exists a local perturbation $h$ which lifts the degeneracy. But then $\mathcal{U} h \mathcal{U}^{\dagger}$ is a local perturbation which lifts the degeneracy of $H_K$ which is a contradiction.
With regard to your last question, the Kitaev superconductor in 1-D (D-class) is protected without requiring to any symmetry. On the other hand, the class DIII does require time-reversal symmetry. If you ignore the symmetry a class-DIII superconductor actually looks like two copies of the Kitaev superconductor, which is supposed to be trivial (because D class has a $Z_2$ classification). In other words, there are actually two Majorana zero modes on the edge, which is equivalent to a regular complex fermion and can be gapped out. But, the term which gaps out the edge is not allowed by time-reversal symmetry. Thus, the class D superconductor is topologically ordered, the class DIII superconductor is only SPT.
[1] https://arxiv.org/abs/1008.5137