Considering a partition to be an ordered $n$-tuple $(m_1, m_2, m_3, ..., m_n)$ with all the numbers $m_i$ natural, $m_1 \le m_2 \le m_3 \le ... \le m_n$, and $m_1+m_2+...+m_n=n$: how many of those $n$-tuples are there?
Also, what is the link between partitions and Cauchy's observation that the number of permutations in $S_n$ that can be written as a product of $k_1$ lenght-1 cycles, $k_2$ lenght-2 cycles, ..., $k_n$ lenght-n cycles (all the cycles being disjoint) is: $$\frac{n!}{k_1!k_2!k_3!\cdots k_n!\cdot 1^{k_1}2^{k_2}3^{k_3} \cdots n^{k_n}}$$
There is a famous generating function for this: I will provide the generating function, then talk a little bit about why it is correct.
The generating function is $$ P(q) = \prod_{k=1}^\infty (1 - q^k)^{-1} = 1 + q +2q^2 + 3q^3 + 5q^4 + 7q^5 + 11q^6 + \cdots. $$
Why is it correct? Well, write each individual term in the product out: The first few are $$ \frac{1}{1 - q} = 1 + q + q^2 + q^3 + q^4 + \cdots $$ and $$ \frac{1}{1 - q^2} = 1 + q^2 + q^4 + q^6 + q^6 + \cdots $$ and $$ \frac{1}{1 - q^3} = 1 + q^3 + q^6 + q^9 + q^{12} + \cdots $$ etc. So what is the coefficient of $q^n$ in the resulting series? It will be all ways of taking terms from some multipland whose total exponent adds up to $n$. If you take a term $q^{mk}$ from $(1 - q^k)^{-1}$ then this should be thought of as $k + \cdots + k$ ($m$ times). In particular, let's look at the coefficient of $q^3$. Then we get $$ (1 + q + q^2 + \color{red}{q^3} + \cdots) \cdots $$ and $$ (1 + \color{red}{q} + q^2 + \cdots)(1 + \color{red}{q^2} + q^4 + \cdots) \cdots $$ and $$ (\color{red}{1} + q + q^2 + \cdots)(\color{red}{1} + q^2 + q^4 + \cdots)(1 + \color{red}{q^3} + q^6 + \cdots) \cdots $$ corresponding to the three partitions $1 + 1 + 1$, $1 + 2$, and $3$.
Note that your condition that the partition be ordered, but that $m_1 \leq m_2 \leq \cdots$ is equivalent to taking an unordered partition which is what I've described here, since we can always rearrange our terms in increasing order.
Note further that a lot of information about this can be found at http://oeis.org/A000041
As for the second part of the question: First note that the conjugacy class of any element $\sigma \in S_n$ yields a partition of $n$ by looking at its cycle decomposition. In particular, this yields a bijection between partitions of $n$ and conjugacy classes of $S_n$. Accordingly, for a fixed partition of $n$ we are looking at determining the size of such a conjugacy class. Now, the group $S_n$ acts on a conjugacy class $C$ via conjugation. The orbit-stabilizer theorem tells us that $$ n! = |S_n| = |C(\sigma)| \cdot |Stab_{S_n}(\sigma)| $$ for any fixed $\sigma \in C(\sigma)$. So if we can determine the order of a stabilizer under the conjugation action, then we are done. If we write $$ \sigma = \underbrace{\sigma_1^1 \cdots \sigma_{k_1}^1}_{k_1} \underbrace{\sigma_1^2 \cdots \sigma_{k_2}^2}_{k_2} \cdots $$ (where the exponents refer to the length of the cycle), then we note that a conjugation which fixes this must
In any case, there are $k_i!$ permutations of the $i$ cycles, and for each of those there are $i$ cyclic permutations. Thus for each $i$, we have $k! i^{k_i}$ permutations which fix all of those. Putting it together, the stabilizer of $\sigma$ has order $$ \prod_{i=1}^n k_i! i^{k_i} $$ which yields what you're looking for; specifically, $$ |C(\sigma)| = \frac{|S_n|}{|Stab_{S_n}(\sigma)|} = \frac{n!}{\prod_{i=1}^n k_i! i^{k_i}} $$