TL;DR: We do not need to inspect all the elements of the hidden subgroup ${\mathcal H}=Aut(G)$. We only need to inspect the elements of the generating set that HSP subroutine has found. An efficient HSP subroutine will return a generating set whose size is polynomial in $\log|\mathcal{H}|$. Finally, note that $\log N!=O(N\log N)$, so even if $Aut(G)\simeq S_N$, we still need to inspect a number of permutations that is polynomial in $N$.
Background
For any finite set $A$, let $S_A$ denote the group of all permutations of $A$. If $G=(V,E)$ with $E\subset V\times V$ is a graph and $\pi\in S_V$ a permutation of its vertices, then set $\pi(G)=(V,\pi(E))$ where $\pi(E)=\{(\pi(u),\pi(v))\,|\,(u,v)\in E\}$. Finally, let $Aut(G)\subset S_V$ denote the subgroup of $S_V$ consisting of vertex permutations $\pi$ that fix $G$, i.e. $\pi(G)=G$.
In the Graph Isomorphism (GI) decision problem we are given two graphs $G_1=(V,E_1)$ and $G_2=(V,E_2)$ with $N$ vertices and are asked to determine whether they are isomorphic, i.e. if there exists a permutation $\pi\in S_V$ such that $G_1=\pi(G_2)$.
In the Hidden Subgroup Problem (HSP) we are given a group ${\mathcal G}$ and a function $f:{\mathcal G}\to X$ to some set $X$ which hides$^1$ an unknown subgroup ${\mathcal H}$ of ${\mathcal G}$ and are asked to provide a generating set for ${\mathcal H}$. There is a subtlety here. Many generating sets for a large group are themselves large, after all ${\mathcal G}$ is a generating set for ${\mathcal G}$. However, an efficient HSP subroutine by definition outputs a generating set whose size is polynomial in $\log|\mathcal{G}|$. This is always possible since, by group theory, every group ${\mathcal G}$ has a generating set with at most $\log_2|{\mathcal G}|$ generators$^2$.
Reduction
Imagine that we have a magic computer that solves the HSP for permutation groups. We will use it to solve GI for two connected$^3$ graphs $G_1$ and $G_2$ as follows. First, create the disjoint union $G=(W,E)$ where $W=V\sqcup V=V_1\cup V_2$ and $E=E_1\sqcup E_2$. Next, run the HSP solver on the magic computer with $\mathcal{G}:=S_W$, $X$ the set of graphs with vertices in $W$ and $f:\mathcal{G}\to X$ defined by $f(\pi):=\pi(G)$. It is an exercise in the application of definitions to show that $f$ hides $Aut(G)$. Therefore, our magic computer returns a set $\mathcal{S}$ that generates $Aut(G)$.
Now, suppose that every generator $\sigma\in\mathcal{S}$ maps $V_1$ to $V_1$. Then it is impossible to use the generators to construct a permutation that sends a $v\in V_1$ to $w\in V_2$. Consequently, in this case, every $\pi\in Aut(G)$ maps $V_1$ to $V_1$ and $V_2$ to $V_2$. Therefore, $G_1$ is not isomorphic to $G_2$. Conversely, if there is a generator $\sigma\in\mathcal{S}$ that sends $v\in V_1$ to $w\in V_2$, then $\sigma$ necessarily maps $V_1$ to $V_2$ and $V_2$ to $V_1$. Therefore, $G_1$ is isomorphic to $G_2$.
Complexity
Thus, we only need to inspect the effect of every $\sigma\in\mathcal{S}$ on every element of $v\in V_1$ in order to determine whether $G_1$ and $G_2$ are isomorphic. Obviously, $V_1$ has size polynomial in $N$. However, $\mathcal{S}$ has size polynomial in $\log|Aut(G)|\leqslant\log|S_N|=\log N!=O(N\log N)$, so $\mathcal{S}$ also has size polynomial in $N$. We conclude that the cost of classical post-processing is also polynomial in $N$.
Remarks
Note that the reduction above means that the HSP subroutine will never be invoked on a complete graph. After all, $G$ is disconnected! Nevertheless, $Aut(G)$ may be $S_N$. Still, as the argument above shows, the complexity of the classical post-processing remains polynomial.
$^1$ Function $f:G\to X$ hides $H$ if $f$ is constant on each coset of $H$ and injective on every transversal.
$^2$ See e.g. $A2.1.1$ on page $611$ in Nielsen & Chuang for proof.
$^3$ Fun exercise: What goes wrong if $G_1$ and $G_2$ are not connected? How to fix the issue?
