Let G be a finite simple group, and let n be the smallest integer such that there exists an embedding of G into the permutation group of n elements. Is this embedding unique up to conjugation?

When you talk about the embedding being unique up to conjugation, I assume that you are asking whether all subgroups of $S_n$ isomorphic to $G$ are conjugate in $S_n$. The answer is not always, but it's not so easy to find counterexamples. You need a simple group with more than one conjugacy class of subgroups of index $n$, where the classes are not all fused by automorphisms of the group. The groups $G_2(q)$ with $q$ not a power of 3 and $q>4$ satisfy this condition. They have two nonisomorphic maximal subgroups with the structure $q^5.{\rm GL}_2(q)$. (When $q$ is a power of 3, these subgroups are fused by the exceptional graph isomorphism. When $q=4$, there is a subgroup $J_2$ of smaller index.) So the smallest counterexample appears to be $G_2(5)$ with $n=3906$. You can find it in the ATLAS of Finite Groups. 


More of a supplement to @Derek's excellent answer: the reason you look for counterexamples of the form he gave is that since your group is simple and the embedding is into a minimal $S_n$ your subgroup must be transitive and primitive. The O'NanScott theorem (which you can google) then gives you a list of possible counterexamples. 


Cayley's theorem states that any group is isomorphic to a subgroup of the symmetric group. This can be seen alternatively from the theory of computability. Any "program" (a group is a set of elements with a group operation) has a representation as a Turing machine, which itself is isomorphic to a subset of a permutation group. 

