Normal subgroup of prime index Generalizing the case $p=2$ we would like to know if the statement below is true.

Let $p$ the smallest prime dividing the order of $G$. If $H$ is a subgroup of $G$ with index $p$ then $H$ is normal.
This is a standard exercise, and the answer is that the statement is true, but the proof is rather different from the elementary way in which the $p=2$ case can be proven.

Let $H$ be a subgroup of index $p$ where $p$ is the smallest prime that divides $|G|$. Then $G$ acts on the set of left cosets of $H$, $\{gH\mid g\in G\}$ by left multiplication, $x\cdot(gH) = xgH$.

This action induces a homomorphism from $G\to S_p$, whose kernel is contained in $H$. Let $K$ be the kernel. Then $G/K$ is isomorphic to a subgroup of $S_p$, and so has order dividing $p!$. But it must also have order dividing $|G|$, and since $p$ is the smallest prime that divides $|G|$, it follows that $|G/K|=p$. Since $|G/K| = [G:K]=[G:H][H:K] = p[H:K]$, it follows that $[H:K]=1$, so $K=H$. Since $K$ is normal, $H$ was in fact normal.
In addition to the things answered here, I just want to add this one. 
Proposition Let $G$ be a finite group and $H$ a subgroup of prime index $p$, with gcd$(|G|,p-1)=1$. Then $G' \subseteq H$.
 Note that this implies that $H \unlhd G$, and that it is in fact sufficient to prove that $H$ is normal, since then $G/H \cong C_p$ is abelian.
Proof  Firstly, we may assume by induction on $|G|$, that $H$ is core-free, that is core$_G(H)=\bigcap_{g \in G}H^g=1$. This means that $G$ can be homomorphically embedded in $S_p$. Let $P \in Syl_p(G)$ and note that because $|S_p|=p \cdot (p-1) \cdots \cdot 1$, $|P|=p$. By the $N/C$-Theorem, $N_G(P)/C_G(P)$ embeds in Aut$(P) \cong C_{p-1}$. By the assumption gcd$(|G|,p-1)=1$, we get that $N_G(P)=C_G(P)$. Since $P$ is abelian we have $P \subseteq C_G(P)$, whence $P \subseteq Z(N_G(P))$. We now can apply Burnside's Normal $p$-complement Theorem, which implies that $P$ has a normal complement $N$, that is $G=PN$ and $P \cap N=1$. Note that $|G/N|=p$. Look at the image of $H$ in $G/N$. Then $G=HN$, or $HN=N$. In the latter case $H \subseteq N$, and $|G:H|=|G:N|=p$, whence $H=N$ and we are done if we can refute the first case. If $G=HN$, then $|G:H \cap N|=|G:N|\cdot|N:H \cap N|=|G:N|\cdot |G:H|=p \cdot p=p^2$, contradicting the fact that $|G| \mid |S_p|$. The proof is now complete.
Corollary 1 Let $G$ be a finite group and let $H$ be a subgroup with $|G:H|=p$, the smallest prime dividing the order of $G$. Then $G' \subseteq H$. In particular, $H$ is normal.
Corollary 2 Let $G$ be a finite group and let $H$ be a subgroup with $|G:H|=p$ and gcd$(|H|,p-1)=1$. Then $H$ is normal.
Observe that this last result renders a well-known result for $p=2$! Finally for fun:
Corollary 3 Let $G$ be a finite group of odd order and $H$ a subgroup with $|G:H|=65537$. Then $H$ is normal.