What exactly does conjugation mean? In group theory, the mathematical definition for "conjugation" is:
$$
(g, h) \mapsto g h g^{-1}
$$
But what exactly does this mean, like in laymans terms?
 A: Actually I would say conjugation is $g\mapsto(h \mapsto g h g^{-1})$, that is, most often one will fix $g$ and say conjugation by $g$ is the map $h \mapsto g h g^{-1}$. Here $g$ is some kind of automorphism of a structure $X$, and $h$ is usually en endomorphism of $X$ (so $g,h$ are maps $X\to X$, where $h$ need not be invertible, though $g$ obviously must be; they're also usually compatible with some structure on $X$).
One can consider an automorphism as a symmetry of the structure $X$, mapping any $x$ to another element $x'=g(x)$ that is (with respect to the structure of $X$) in every way similar to $x$. Conjugation of $h$ by some $g$ now means finding the map $h':X\to X$ corresponding to $h$ under the symmetry of $g$. Explicitly, given $x'\in X$ one must first find the element $x=g^{-1}(x')$ where it came from under the symmetry, then apply $h$ to $x$, and finally find the element $g(h(x))$  corresponding to $h(x)$ under the symmetry. All in all this maps $x'$ to $g(h(g^{-1}(x)))=h'(x)$, and so we've transformed the map $h$ into its symmetric counterpart $h'=g\circ h\circ g^{-1}$.
If one is doing abstract group theory, then one considers elements $g$ of a group independently of any structure $X$ of which it might be the automorphism group (one can always concoct such a structure, but it is not unique). So one cannot in this case give the above description using elements $x,x'$, but the map $h \mapsto g h g^{-1}$ can be defined in terms of the group only (where now necessarily $h$ has to be in the group). Note however that conjugation does not apply only in the group setting; one could well take $g$ to be any invertible matrix and $h$ any matrix of the same size; this is also called conjugation.
A: The following is equivalent to the second paragraph of Marc van Leeuwen's answer, but I think it might help emphasize how natural conjugation really is.  With notation as in Marc's answer, let me write $h'$ for the conjugate $ghg^{-1}$.  Then $h'$ is obtained by shifting $h$ along $g$ in the sense that, whenever $h$ sends an element $x\in X$ to another element $y$, then $h'$ sends $g(x)$ to $g(y)$.  If, as people sometimes do, one regards a function $h$ as a set of ordered pairs, then $h'$ is obtained by applying $g$ to both components in all those ordered pairs.  
A: Conjugation is an important construction in group theory. Conjugation defines a group action of a group on itself and this often yields useful information about the group. For example, this technique is how the Sylow Theorems are proven. More importantly, a normal subgroup of a group is a subgroup which is invariant under conjugation by any element. Normal groups are extremely important because they are the kernels of homomorphisms and it is possible to take the quotient of a group and one of its normal subgroups. 
A: The best way I've found to think of conjugation is "looking at the same group from a different point of view". I'm going to talk about this in a very intuitive way, because it is an idea that is hard to formalise. Let me know if you want some more concrete examples. This also helps understand what conjugacy classes are, as well as normal subgroups. Conjugacy classes are sets of things which "all look the same when viewed from a different way" and normal subgroups are subgroups for which the elements "each look the same when you change you perspective". This is most appropriate when the group in question acts on things, because in that case conjugation normally gives a new element with a very similar action.
Probably the easiest example to show what I'm saying is with $Mat_n(F)$ The group of $n\times n$ matrices over a field $F$. (and you can think of  the group acting on the $n\times n$ vectors over the field $F$ if you want. Here, conjugation by an invertible is the same as a change of basis. This tells us that the conjugate of any matrix gives a new matrix which represents the same linear map (so the action on the group is of exactly the same type. Even though it will now map the same vector to a different one as the preconjugated matrix, if you write the original vector in terms of the new basis, the new matrix will map it to the same vector as before, represented in the new basis). The actual nature of the element isn't changed by conjugation, but to see that you now have to look at it with your new point of view being your new basis.
Another case is the Symmetric group $S_n$. (which acts on a set of $n$ labelled points) Here, conjugation of an element $\rho$ by an element $\sigma$ say, amounts gives the new map $\sigma^{-1}\rho\sigma$ which means "change the labelling of the n elements according to the transformation $\sigma$, then perform $\rho$ on the same set but according to their new labels, then send the re-label this transformed set by "undoing" $\sigma$. This explains the fairly commonly known result that conjugates in $S_n$ all have the same cycle type. This is because, in some fundamental way, they represent the same transformation. The reason the actual components of the cycle types are different is because they are the same transformation, if you label the set of $n$ points differently.
We can see this even more concretely in $D_n$ the dihedral group of order $n$, the set of symmetries of a regular $n-$gon. Here, whenever we conjugate a reflection we get another reflection. If $n$ is odd, each line of reflectional symmetry runs through one edge and one vertex, so all reflections are conjugate but if $n$ is even a line of reflectional symmetry runs through either two edges or two vertices, and then the conjugacy classes of elements splits into the set of reflections running through edges and the set of reflections running through vertices. This is because the two kinds of reflections are fundamentally different (compare a square to a pentagon to see what I mean)
A: It gives you an idea of how commutative your group is. For example, if your group is $\mathbb Z$ with addition then for all $g,h$ we have $ghg^{-1} = h$. Like for example for $g=13, h=4$ you have $+13 + 4 - 13 = 4$.
On the other hand, if your group is not commutative then $ghg^{-1}$ might be not equal to $h$. For example if your group is the symmetric group, that is, the group of permutations, say of $4$ elements and $h=(235)$ and $g=(13)$ then $(13)(235)(13) \neq (235)$. The former is the function $1 \mapsto 5, 2 \mapsto 1, 3 \mapsto 3, 4 \mapsto 4, 5 \mapsto 2$ but the latter, $h$, is the function $1 \mapsto 1, 2 \mapsto 3, 3 \mapsto 5, 4 \mapsto 4, 5 \mapsto 2$.
