Prof. Lee in p. 30 of his "Riemannian Manifolds" says:
"Given a pseudo-Riemannian metric $g$ and a point $p \in M$, by a simple extension of the Gram-Schmidt algorithm one can construct a basis $(E_1, \dotsc, E_n)$ for $T_p M$ in which $g$ has the expression $$ g = -(\varphi^1)^2 - \dotsb - (\varphi^r)^2 + (\varphi^{r+1})^2 + \dotsb + (\varphi^n)^2 $$ for some integer $0 \le r \le n$."
However, I don't think it is quite that simple. In the Riemannian case, the coordinate frame $\partial_i$ forms a local frame, and applying the Gram-Schmidt algorithm to that brings the metric to the above form. But in the semi-Riemannian case, the coordinate vectors $\partial_i$ can all be null, e.g.
$$g = 2 \, du \, dv\text{.}$$
It seems to me that one would need to construct some local frame first in order to apply Gram-Schmidt.
An alternate way would be to represent the metric $g$ by a matrix and then eigendecompose it, i.e. represent it by $A D A^{-1}$ where $D$ is $\operatorname{diag}(\lambda_1, \dotsc, \lambda_n)$, where $\lambda_i$ are the (real) eigenvalues in ascending order. From that we can construct a local frame, and then rescale to bring $g$ to the above form. But this way doesn't involve Gram-Schmidt at all, as far as I can tell.
Am I missing something?
You're right that it's not quite as simple as I made it appear. The correct generalization of the Gram-Schmidt algorithm uses the idea of a "nondegenerate basis": If $V$ is a finite-dimensional vector space endowed with a nondegenerate scalar product $g$, an ordered basis $(E_1,\dots,E_n)$ for $V$ is said to be nondegenerate if for each $k=1,\dots, n$, the scalar product $g$ restricts to a nondegenerate scalar product on the subspace spanned by $(E_1,\dots,E_k)$.
The two facts you need to make this work are
Proving these is only a little more complicated than proving the Gram-Schmidt algorithm itself. The nondegeneracy hypothesis guarantees that the expressions that appear in the denominators in the Gram-Schmidt algorithm are always nonzero.