If $H \leq G$ and $|H|=p$ where $p$ is prime, is $H$ a normal subgroup? Currently reading Gallian's book "Contemporary Abstract Algebra" and while reading the section on Normal Subgroups, I made myself this question and I can't see that there is an exercise or anything in the book where they ask me this, so I was wondering. 
 A: No, and the already given answer has a nice example. But I thought I would just add a word on how to broach your own question: You are asking about whether, under some conditions, a subgroup must be normal. If true, then it would be nice to prove; if false, then it would be nice to find a counterexample. A while back I wrote another post (MSE 1214719) on how to find a counterexample for another group theory question; it may be worth a read.
In this case, an important fact to remember is that in an abelian group, every subgroup is a normal subgroup. So, if you are going to look for a counterexample, then you would be best suited to begin your search in a nonabelian group.
Recall - or read for the first time, in which case you may wish to prove them! - the following facts: first, the smallest nonabelian group is $S_3$, which has six elements; second, a group is divisible by the order of any of its subgroups (this is Lagrange's Theorem), so subgroups of $S_3$ must have order $1$, $2$, $3$, or $6$ (and, in this case, each exists); third, if the order of a group divided by the order of a subgroup yields $2$, then the subgroup is normal (I've heard this called the index two theorem).
So: If we start with a nonabelian group, then it makes sense to try the smallest one, i.e., $S_3$ with its $6$ elements. For it to serve as a counterexample, you want it to have prime order to satisfy the constraints in your query - so we should pick a subgroup of size $2$ or $3$ - and we want it not to be normal - so we should avoid picking a subgroup of size $3$ in this case, since $6/3 = 2$ would make the subgroup normal by the above-mentioned index two theorem.
All this would lead one to pick exactly one of the two element subgroups of $S_3$, which is precisely the counterexample given in an earlier answer! Still, hopefully this write-up gives some insight into how you can broach your next conjecture.
A: This is not true. Consider a subgroup $H$ generated by a $2$-cycle $(12)$ in a symmetric group $S_3.$ Then
$$H \cdot (13)=\{(12), \text{id} \} \cdot (13) =\{(132), (13)\},$$
$$(13) \cdot H=(13) \cdot \{(12), \text{id} \}= \{(123), (13)\}.$$
Thus,
$$ H \cdot (13) \neq (13) \cdot H,$$
implying that $H$ is not normal in $S_3.$
A: $H$ is not necessarily normal. Let $G = S_3$ and $H = \langle (1 \ 2) \rangle$. Then $|H| = 2$ but $H$ is not normal. For instance:
$$(1 \ 2 \ 3)(1 \ 2)(1 \ 2 \ 3)^{-1} = (1 \ 2 \ 3)(1 \ 2)(2 \ 1 \ 3) = (2 \ 3) \notin H.$$

A deeper investigation: Suppose $|G| = pm$ where $p$ is prime and does not divide $m$.
$G$ will necessarily have at least one subgroup $H$ of order $p$. In this case, $H$ will be normal if and only if $H$ is the only subgroup of order $p$. These observations follow from the Sylow Theorems. 
When $G = S_3$: We can use this observation to say that since there are $3$ subgroups of order $2$, none of them are normal.
