The problem I'm having is the line ``Any p-cycle can be written as ##(1\;2\;\cdots\;p)## by relabeling the objects being permuted by applying an overall conjugation on ##S_p##''.

An example helps me to understand:

Suppose I have ##R=(3\;5),Q=(4\;1\;2\;5\;3)\in S_5##. Now, I take this to mean if I conjugate the entire group, ##\sigma S_5 \sigma^{-1}## such that ##\sigma Q \sigma^{-1}=(1\;2\;3\;4\;5)##, then I've effectively ``relabeled'' ##Q## with ##(1\;2\;3\;4\;5)##. That's easy to accomplish since in general for ##\rho=(a\;b\;c\;d\;e)##, ##\sigma\rho\sigma^{-1}=(\sigma(a)\;\sigma(b)\;\sigma(c)\;\sigma(d)\;\sigma(e))##. Then let ##\sigma=(1\;2\;3\;5\;4)## and then we have ##(1\;2\;3\;5\;4)(4\;1\;2\;5\;3)(4\;5\;3\;2\;1)=(1\;2\;3\;4\;5)##. Therefore I assume this all means:

since conjugation is an automorphism (it's a bijection) and where ##(h\;k)## is the conjugation of ##(3\;5)## and just accepting for the moment if I can get it to that form, it generates the group via the second part of the theorem which I will accept for now.

The second part of the theorem is proven as Theorem 2.8 of what you linked.

Given that, you just need to write out the formulas by which an arbitrary element g of the group can be expressed in terms of a transposition T and a p-cycle C by first using Theorem 2.8 to express the conjugate of g in terms of another transposition (why not choose (1 2) WLOG) and the standard p-cycle.