First of all let's call the $2$-cycle $(a,b)$ and write $\sigma=(a,b)\sigma_0$ when $\sigma_0$ is a permutation in which $a,b$ are fixed points. Now we are going to prove the first part.
Assume $\tau$ is conjugate to $\sigma$ in $S_n$. We want to show they are conjugate in $A_n$ as well. We know there is a permutation $\lambda\in S_n$ such that $\tau=\lambda\sigma\lambda^{-1}$. If $\lambda\in A_n$ then $\sigma$ and $\tau$ are conjugate in $A_n$, nothing left to prove. Now suppose $\lambda\notin A_n$, which means $\lambda$ is an odd permutation. Now let $\mu=\lambda(a,b)$. It is an even permutation as a product of odd permutation, which means $\mu\in A_n$. And now note that:
$\mu\sigma\mu^{-1}=\lambda(a,b)(a,b)\sigma_0(a,b)\lambda^{-1}=\lambda\sigma_0(a,b)\lambda^{-1}=\lambda(a,b)\sigma_0\lambda^{-1}=\lambda\sigma\lambda^{-1}=\tau$
I simply used the fact that disjoint cycles commute, and of course that $(a,b)^{-1}=(a,b)$. So $\sigma$ and $\tau$ are conjugate in $A_n$ as well.
As for the second part, I'll show two possible ways to solve it. The first way: take the permutation $(1234567)$. The permutations which are conjugate to it have the form $\lambda(1234567)\lambda^{-1}=(\lambda(1)\lambda(2)...\lambda(7))$. Now try to find what $\lambda$ needs to be in order to get $\lambda(1234567)\lambda^{-1}=(2134567)$. Such a permutation must satisfy $(\lambda(1)...\lambda(7))=(2134567)$. There are $7$ such permutations. Find them and you will get they are all odd. Hence $(1234567)$ and $(2134567)$ are conjugate in $S_7$ but not in $A_7$.
Now the second way to solve the second part: again, let $\sigma=(1234567)$. Suppose its conjugacy class in $S_7$ equals to its conjugacy class in $A_7$. That means $(12)\sigma(12)=\lambda\sigma\lambda^{-1}$ for an even permutation $\lambda$. From here we get that $\sigma$ commutes with $(12)\lambda$, which means $\sigma$ commutes with an odd permutation. On the other hand, we know that $\sigma=(1234567)$ is conjugate to $6!$ different permutations in $S_7$, which are all the permutations with same cycle structure as $\sigma$. By the Orbit-Stabilizer theorem we get that $\sigma$ commutes with $\frac{7!}{6!}=7$ permutations. But we also know it commutes with $id,\sigma,\sigma^2,...,\sigma^6$ which are $7$ different permutations. But as $\sigma$ commutes only with $7$ permutations we conclude that it can't commute with anything else. Hence $\sigma$ commutes only with even permutations which is a contradiction.
This is an interesting question and I believe is an open problem in general. The literature on Cayley graphs of symmetric groups generated by transpositions would be relevant. The quantity you are interested in - the number of permutations that are a product of exactly $k$ (and no fewer) transpositions - is the number of vertices in the complete transposition graph whose distance to the identity vertex is exactly $k$.
More specifically, let $S$ be the set of all transpositions in $S_n$ ($n \ge 3)$. The complete transposition graph is the Cayley graph $G = Cay(S_n,S)$, which is defined to be the graph with vertex set $S_n$ and with edge set $\{(h, sh): h \in S_n, s \in S \}$. Define $G_i(v)$ to be the set of vertices in $G$ whose distance to vertex $v$ is exactly $i$. Let $e$ denote the identity permutation in $S_n$. Then $G_0(e) = \{e\}$, $G_1(e)$ is the set $S$ of all ${n \choose 2}$ transpositions in $S_n$, and $G_2(e)$ is the set of all permutations in $S_n$ which are either 3-cycles or a product of two disjoint transpositions.
The open source software SAGE (sagemath.org) contains, among other things, built-in functions to create Cayley graphs and output the size of the $i$th layer $G_i(v)$ in the distance partition of $G$ with respect to a vertex $v$.
Best Answer
Yes, there is a linear time algorithm. Skipping seen entries ensures each permutation entry is referenced at most $2$ times, so this is linear time.
You cannot determine the number of cycles a permutation has in sublinear time. Indeed, suppose that you have only looked at $n-2$ entries of the permutation. Depending on the permutation for the remaining $2$ unseen items, there will be one of two different possible answers for the question "How many cycles does the permutation have?". The two answers differ by one, since switching two elements either mergers two cycles or breaks one apart. This shows an algorithm cannot always succeed with this work alone. Therefore, at least $n-2$ look-ups are necessary, so any algorithm must be $\Omega(n)$.