I know that every permutation of a finite set can be decomposed into product of disjoint cycles and every cycle can be decomposed into product of transpositions (cycles of length 2). However the decomposition into transpositions is not unique. I'm aware of at least two "algorithms" for decomposing a cycle into a product of transpositions:
$$(a_1, a_2, \ldots, a_n) = (a_1, a_n)(a_1, a_{n - 1}) \cdots (a_1, a_2)$$
$$(a_1, a_2, \ldots, a_n) = (a_1, a_2)(a_2, a_3) \cdots(a_{n - 1}, a_n)$$
Is there a theorem for counting all possible ways of decomposing a cycle into a product of transpositions (given that I only care about decomposition into $n-1$ transpositions)?
If you think of a transposition $(ij)$ as giving an edge for a graph on the vertex set $[n]=\{1,\ldots,n\}$, then you easily see that a product of $n-1$ transpositions forms an $n$-cycle exactly when the underlying graph is a spanning tree on $[n]$. By Cayley's theorem there are $n^{n-2}$ of those. The number of "products" of transpositions that give a big cycle is thus $n^{n-2}\times (n-1)!$ because one also needs to choose the order of the transpositions. So the answer (count per fixed cycle) is $$ \frac{n^{n-2}\times (n-1)!}{(n-1)!}=n^{n-2} $$ as figured out by joriki in the comments. Note that I also used the obvious fact this number of factorizations is the same for all $n$-cycles because the latter are the same up to conjugation.
Note that there is famous article by Dénes which proves the count bijectively: "The representation of a permutation as the product of a minimal number of transpositions and its connection with the theory of graphs", Publ. Math. Institute Hung. 4 (1959), 63–70.
In fact, I misquoted Dénes. The truly bijective argument is due to Moskowski in "A Solution to a Problem of Dénes: a Bijection Between Trees and Factorizations of Cyclic Permutations" in EJC 1989.