In Sage, the symmetric group is a list. For instance if $G$ = SymmetricGroup($3$), we have
\begin{align*} G[0] & = e \\ G[1] & = (1,3,2)\\ G[2] & = (1,2,3) \\ G[3] &= (2,3)\\ G[4] &= (1,3) \\ G[5] & = (1,2) \end{align*}
I am simply wondering what is the ordering that Sage is using. I am fairly certain it's not "random".
Sage doesn’t have specific code to iterate over the symmetric group $S_n$; it treats $S_n$ like any other permutation group and uses a general algorithm to generate all elements of a permutation group from its generators.
I’ll be linking to lines from the following source files below:
Sage code that constructs $S_n$ as a permutation group: sage.groups.perm_gps.permgroup_named
Sage code that generates the elements of permutation groups sage.groups.perm_gps.permgroup
GAP code that constructs a stabilizer chain for permutation groups: stbc.gi and stbc.gd
The $n$-cycle $(1\ldots n)$ and the transposition $(12)$ are used as generators of $S_n$ (here). Sage calls GAP to compute a stabilizer chain and a corresponding strong generating set for the permutation group. These concepts are explained in the GAP manual section Stabilizer Chains and the Wikipedia article on strong generating sets. The code that does this (starting here) is rather involved, and I don’t know how it works, but for $n\ge5$ the “strong generating system” that is computed (here) from the results has a regular structure. Each element $L_k$, with $1\le k\le n$, is a list of $k$ permutations $\sigma_{kl}$, with $1\le l\le k$, each of which is a cycle or a power of a cycle, as follows:
$$ \sigma_{ij}= \begin{cases} (n-k+l,\dotsc,n-k+1)&k\lt n-1\;,\\ (n,\dotsc,2)^{l-1}&k=n-1\;,\\ (n,\dotsc,1)^{l-1}&k=n,l\lt3\;,\\ (n,\dotsc,1)^{l-2}&k=n,l\gt3\;,\\ (12)&k=n,l=3\;.\\ \end{cases} $$
For instance, for $n=5$, this is
\begin{eqnarray} L_1&=&(())\;,\\ L_2&=&((),(54))\;,\\ L_3&=&((),(43),(543))\;,\\ L_4&=&((),(5432),(53)(42),(5234)\;,\\ L_5&=&((),(54321),(12),(53142),(52413))\;. \end{eqnarray}
This is obviously rather arbitrary and dependent on implementation details, as Sean Eberhard emphasizes in an answer on MO.
The group elements are then produced (here) as products $L_{1,l_1}\circ\dotsb\circ L_{n,l_n}$ of $n$ factors, one from each list, one group element for each of the $n!$ tuples $(l_1,\dotsc,l_n)$ in lexical order. Thus, for instance for $n=5$ the first few elements are
$$ (),(54321),(12),(53142),(52413),(5432),(5432)\circ(54321)=(153)(24),(5432)\circ(12)=(12543). $$
The strong generating systems for $n\lt5$ are different. For $n=2$
\begin{eqnarray} L_1&=&(())\;,\\ L_2&=&((),(21))\;,\\ \end{eqnarray}
for $n=3$
\begin{eqnarray} L_1&=&(())\;,\\ L_2&=&((),(32))\;,\\ L_3&=&((),(321),(312))\;,\\ \end{eqnarray}
and for $n=4$
\begin{eqnarray} L_1&=&(())\;,\\ L_2&=&((),(43))\;,\\ L_3&=&((),(234),(243))\;,\\ L_4&=&((),(13)(24),(14)(23),(12)(34))\;. \end{eqnarray}