How many orthogonal matrices are there
let us count the number of constraints:
(a) to make the first column orthogonal to the remaining $n-1$ columns, you need $n-1$ constraints. al together one needs $(n-1)+(n-2) + \cdots + 2 + 1=\frac12 n(n-1).$
(b) to make all columns of length $1,$ one needs $n$ constraints.
therefore, to make an $n \times n$ orthonormal matrix, you will have $$n^2 -\frac12n(n-1) - n=\frac{n(n-1)}{2}$$ free parameters. for example, you have only one free variable to make a $2 \times 2$ orthogonal matrix. for $n = 3,$ it is $3$ free variables.
for an orthogonal matrix, you don't need to make the columns length one. so there will be $$\frac{n(n+1)}2$$ free variables.
It's not too hard to show that the space $O(n, \Bbb F)$ of $n \times n$ orthgononal matrices over the field $\Bbb F$ (which we take to be $\Bbb R$ or $\Bbb C$) is an $\frac{1}{2}n (n - 1)$-dimensional (resp., real or complex) manifold, which in particular means that for any orthogonal matrix $A \in O(n)$ there is a local homeomorphism between some open neighborhood of $A$ and $\Bbb R^{\frac{1}{2} n (n - 1)}$. (Here, the topology on $O(n, \Bbb F)$ is just the subspace topology regarding as a subset of the space $M(n, \Bbb F)$ of $n \times n$ matrices over $\Bbb F$, which we identify with the Euclidean/complex space $\Bbb F^{n^2}$ in the obvious way.) Informally, this just means that locally $\frac{1}{2} n (n - 1)$ coordinates is enough to specify a particular orthogonal matrix, and so we might expect that generically $\frac{1}{2} n (n - 1)$ entries is enough, at least up to some discrete choice(s).
That number is suggestive (even more so if one carries out the above computation): An $n \times n$ matrix has precisely $\frac{1}{2} n (n - 1)$ strictly upper triangular entries, that is, entries $a_{ij}$ with $i < j$. Suppose we have specified these; then, we can use (inductively) the fact that a matrix is orthogonal iff its columns are orthonormal to attempt to construct an orthogonal matrix with those entries. For convenience, denote the $i$th column of $A$ by ${\bf a}_i$.
The only entry not specified in the last column, ${\bf a}_n$, is $a_{nn}$, but we can recover this entry---up to sign---using that, by orthonormality, ${\bf a}_n \cdot {\bf a}_n = 1$: rearranging gives that
$$a_{nn}^2 = 1 - \sum_{i = 1}^{n - 1} a_{in}^2.$$
(We can see in the real case that the specified entries must satisfy $\sum_{i = 1}^{n - 1} a_{in}^2 \leq 1$.)
Next, all of the entries of the penultimate column, ${\bf a}_{n - 1}$, are given except for $a_{n - 1, n - 1}$ and $a_{n, n - 1}$, and these are determined up to sign by the fact that, again, we must have ${\bf a}_{n - 1, n - 1} \cdot {\bf a}_{n - 1, n - 1} = 1,$ and also the orthogonality condition ${\bf a}_{n - 1, n - 1} \cdot {\bf a}_{nn} = 0.$ In coordinates, these conditions can be written as the system $$\sum_{i = 1}^n a_{i, n - 1} a_{i j} = 1, \quad j \in \{n - 1, n\};$$ this determines one quadratic and one linear condition on the two unknowns and again determines them up to a sign. We can then proceed leftward, determining each of the remaining columns.
Example It's instructive to carry out this procedure for $n = 2$ (we'll stick to the real case to recover something familiar): In this case, there is only one strictly upper triangular entry, namely, $a_{12}$. By the above it must satisfy $a_{12}^2 \leq 1$, that is, $-1 \leq a_{12} \leq 1$, so we can write $a_{12} = -\sin \theta$ for some $\theta$. Now, the orthogonality condition gives us that the $(2, 2)$ entry satisfies $$1 = a_{12}^2 + a_{22}^2 = \sin^2 \theta + a_{22}^2,$$ and so by the Pythagorean Identity we have $a_{22} = \pm \cos \theta$. By replacing $\theta$ with $\pi - \theta$ (which does not change the value of $-\sin \theta$) if necessary, we may assume $a_{22} = \cos \theta$.
Now, by orthogonality the entries in the first column satisfy $$0 = {\bf a}_1 \cdot {\bf a}_2 = a_{11} a_{12} + a_{21} a_{22} = -a_{11} \sin \theta + a_{21} \cos \theta.$$ This defines a linear equation in $a_{11}, a_{21}$, and so we conclude that we must have $a_{11} = t \cos \theta$ and $a_{21} = t \sin \theta$ for some $t$. Now, the normality condition gives $$1 = {\bf a}_1 \cdot {\bf a}_1 = (t \cos \theta)^2 + (t \sin \theta)^2 = t^2,$$ and hence $t = \pm 1$.
Putting this all together gives us a parameterization of all $2 \times 2$ real orthogonal matrices: $$\begin{pmatrix} \pm \cos \theta & -\sin \theta \\ \pm \sin \theta & \cos \theta\end{pmatrix}.$$ The determinant of such a matrix is $\pm 1$, so a choice of $+$ for the entries in the first column gives a rotation (a special orthogonal matrix), and a choice of $-$ gives a reflection.
Remark This question suffers from the complication that the answer can actually depend on the given entries themselves: For example, if one specifies that a given $n \times n$ real orthogonal matrix has diagonal entries $1, \ldots 1$, by orthogonality all other entries are zero, despite that we'd only specified $n$ entries. From this point of view, the answer $\frac{1}{2} n (n - 1)$ is only the number required for a generic orthogonal matrix.