The commutativity condition $\mu\pi=\pi\mu$ can be written as $\mu\pi\mu^{-1}=\pi$. Thus a permutation $\pi$ commutes with $\mu$ if and only if relabeling the cycle structure of $\pi$ according to $\mu$ leaves $\pi$ invariant. That means that for a given cycle of $\pi$, either the cycle has to have even length and pairs of elements at maximal distance from each other in the cycle must be mapped to each other by $\mu$, or the cycle has to be matched with another cycle of the same length and $\mu$ has to map the elements of the cycles to each other in order. (In particular, $\pi$ must have an even number of cycles of every odd length; note the similarity to the condition for a permutation to be the square of some permutation, which is that there must be an even number of cycles of every even length.)
There are $2^kk!$ such permutations, and they are in bijection with $\mathbb Z_2^k\times S_k$. The permutation in the centralizer of $\mu$ corresponding to $(v,\rho)\in\mathbb Z_2^k\times S_k$ is generated from the cycle structure of $\rho$ by making binary choices according to the elements of $v$. For each cycle $\gamma$ of $\rho$, the element $v_i$ corresponding to the least element $i$ in $\gamma$ determines whether $\gamma$ gets cloned to form a pair of cycles mapped to each other under relabeling with $\mu$, or whether $\gamma$ gets doubled in length to form a cycle mapped to itself under relabeling with $\mu$. The elements $v_j$ corresponding to the remaining elements $j\ne i$ in $\gamma$ determine whether $j$ or $n+1-j$ takes the place of $j$ in the cloned or doubled cycle(s).
The key is to look at how conjugation affects permutations of a given cycle type:
$$g=(a_1~a_2~\cdots~a_{\lambda_1})(b_1~b_2~\cdots~b_{\lambda_2})\cdots(c_1~\cdots~c_{\lambda_r}); \\
\sigma g\sigma^{-1}=(\sigma(a_1)~\sigma(a_2)~\cdots~\sigma(a_{\lambda_1}))\,\cdots(\sigma(c_1)~\cdots~\sigma(c_{\lambda_r})).$$
The first line denotes the disjoint cycle representation of an arbitrary $g\in S_n$. Thus, conjugation may only permute cycles of the same length in the representation. Let's revamp our notation:
$$g=a_{1,1}a_{1,2}\cdots a_{1,e_1}\cdots a_{s,1}\cdots a_{s,e_s},$$
where $a_{k,1},\cdots,a_{k,e_k}$ denote the $e_k$ cycles of length $\lambda_k$ in the decomposition, and $g$'s cycle type is
$$\lambda=\big(\underbrace{\lambda_1,\cdots,\lambda_1}_{e_1},\cdots,\underbrace{\lambda_s,\cdots,\lambda_s}_{e_s}\big)\vdash n.$$
The $\lambda_i$s are distinct so that the $e_i$s describe their multiplicities in the integer partition $\lambda$ of $n$.
Fix written representations of the cycles i.e. $a_{t,\ell}=(a_{t,\ell}^{(1)}~a_{t,\ell}^{(2)}~\cdots~ a_{t,\ell}^{(\lambda_{\large t})})$ for $1\le t\le s$ and $1\le\ell\le e_t$; denote, for an arbitrary element $\tau\in S_{e_1}\times\cdots\times S_{e_s}=E$, the induced permutation $\phi(\tau)\in S_n$ that sends $a_{t,\ell}^{(f)}\mapsto a_{t,\tau_{\large t}(\ell)}^{(f)}$, again for each index $1\le t\le s$, $1\le \ell\le e_t$. Thus the inclusion $\phi(E)\subseteq C(g)$ holds. The only other ways to not affect $g$'s structure is to cycle through its disjoint cycles, but note these cyclings can all be done independently from each other. We therefore deduce
$$C(g)=\left\langle \underbrace{\phi(S_{e_1}\times\cdots\times S_{e_s})}_E,\underbrace{\prod_{t=1}^s\prod_{\ell=1}^{e_t}\langle a_{t,\ell}\rangle}_{P}\right\rangle.$$
Observe the cyclic groups generated in the products in $P$ are each trivially intersecting, so the internal product is in fact direct. The elements of $E$ don't slide past those of $P$ without a fight, however; they act on them so that we are creating an unrestricted internal wreath product.
Note then that every element of $C(g)$ can be written as $\alpha\beta$ with $\alpha\in E$ and $\beta\in P$.
We say unrestricted because the arguments here generalize to symmetric groups of arbitrary cardinality, with care taken to only allow infinite products of disjoint cycles and replace $\lambda_i$s and $e_i$s with cardinal numbers as need be. In conclusion,
$$C(g)\cong \prod_{t=1}^s (C_{\lambda_{\large t}}\wr S_{e_{\large t}}),\quad \#C(g)=\prod_{t=1}^s \lambda_t^{e_t}e_t!$$
edit: fixed notation explanation
Best Answer
I will assume permutations act on the right. Throughout $i,j$ will refer to any integers with $1\le i,j\le n$.
Let $\sigma,\omega\in S_n$. Denote $\sigma^\omega=\omega^{-1}\sigma\omega$ and notice $(i^\omega)^{(\sigma^\omega)}=(i^\sigma)^\omega$ so if, for example, $\sigma=(x_1,\ldots,x_r)$ is a cycle then $\sigma^\omega=(x_1^\omega,\ldots,x_r^\omega)$.
Write $\sigma_1=(1,2,\ldots,n)$ and $\sigma_2=(1,2,\ldots, n-1)$. I will answer both interpretations of the question, so I will calculate $C_{S_n}(\sigma_1)$, $C_{S_n}(\sigma_2)$ and $C_{S_n}(\{\sigma_1,\sigma_2\})=C_{S_n}(\sigma_1)\cap C_{S_n}(\sigma_2)$.
Suppose $\omega\in C_{S_n}(\sigma_1)$, so $\sigma_1^\omega=\sigma_1$. From the above, $\sigma_1=\sigma_1^\omega=(1^\omega,\ldots,n^\omega)$. Say $1\le i\le n-1$, then $i^{\sigma_1}=i+1$ and $n^{\sigma_1}=1$. In particular if $i^\omega=j$ then (modulo $n$) $(i+1)^\omega=j+1=i^\omega+1$. Hence $\omega\in\langle \sigma_1\rangle$, but $C_{S_n}(\sigma_1)\supseteq\langle \sigma_1\rangle$ so $C_{S_n}(\sigma_1)=\langle \sigma_1\rangle$.
Suppose $\omega\in C_{S_n}(\sigma_2)$, then by the above $(n^\omega)^{\sigma_2}=(n^\omega)^{(\sigma_2^\omega)}=(n^{\sigma_2})^\omega=n^\omega$. The only fixed point of $\sigma_2$ is $n$ so $n^\omega=n$. Therefore $\omega\in S_{n-1}$ so we are reduced to the $\sigma_1$ case (but for $n-1$) so $C_{S_n}(\sigma_2)=\langle \sigma_2\rangle$.
Finally we have $C_{S_n}(\{\sigma_1,\sigma_2\})=C_{S_n}(\sigma_1)\cap C_{S_n}(\sigma_2)=\{1_{S_n}\}$