Many texts say that an observable should be represented by a hermitian operator. That is sufficient, but not necessary. More generally, we can use any operator that can be expressed as a linear combination of mutually commuting projection operators. Such an operator is called a normal operator. A normal operator $N$ is most simply characterized by the fact that it commutes with its own adjoint: $N^*N = NN^*$. Examples of normal operators include hermitian operators, individual projection operators, and unitary operators.
Here's an example to illustrate this idea. If $P_1,P_2,...$ are mutually orthogonal projection operators, then the operator
$$
A = a_1 P_1 + a_2 P_2 + \cdots
$$
is a normal operator for any choice of (possibly complex) coefficients $a_k$. The eigenvectors of this operator are mutually orthogonal because the projection operators $P_k$ are. If the coefficients are real, then $A$ is self-adjoint (hermitian). But what really matters in quantum theory is the projection operators $P_k$. These are what determine the various possible outcomes of the measurement and the relative frequencies of those outcomes. The coefficients $a_k$ are just convenient labels for the outcomes, making it possible to define statistics like mean values and standard deviations.
Using only self-adjoint operators is sufficient, because allowing complex coefficients is only allowing a more general way of labelling the various implied projection operators. Nature doesn't care how we label things.
In the first paragraph, I said "mutually commuting projection operators", which is more general than "mutually orthogonal projection operators." The latter implies the former, but not conversely. The former is needed in order to include observables like the position operator in non-relativistic quantum mechanics, which does not have (normalizable) eigenvectors. However, it still implicitly defines projection operators like
$$
P\psi(x)=\begin{cases} \psi(x)&\text{ if }x\in R\\
0 &\text{otherwise},
\end{cases}
$$
where $R$ is some region of space. We can think of the usual position operator $X$ as a convenient single-operator representation of this whole algebra of mutually commuting projection operators. It's the projection operators that we use in the measurement postulates. The fact that any normal operator implicitly defines such a set of mutually commuting projection operators is the subject of the spectral decomposition theorem.
Given any observable $A$, if $P$ is one of the projection operators that it implicitly defines (through the spectral decomposition theorem), then a measurement of $A$ will result in a state $|\psi'\rangle$ that satisfies either $P|\psi'\rangle = |\psi'\rangle$ or $(1-P)|\psi'\rangle=|\psi'\rangle$. (I'm not trying to advocate any particular interpretation of quantum theory here; I'm just trying to be concise.) In terms of the state $|\psi\rangle$ prior to the measurement, the relative frequencies of these two possible outcomes are
$\psi(P)$ and $\psi(1-P)$, respectively, using the abbreviation
$$
\psi(\cdots)\equiv\frac{\langle\psi|\cdots|\psi\rangle}{\langle\psi|\psi\rangle}.
$$
The point here is that we don't need to worry if $A$ doesn't have a complete set of (normalizable) eigenstates. As long as $A$ is a normal operator, we can still use the corresponding projection operators to make useful predictions, because each of the projection operators has (normalizable) eigenvectors. As long as they all commute with each other, we can think of this whole set of projection operators as a bunch of mutually compatible observables, each of which has only two possible outcomes.
