Act 1, 3 and 5 mercs have the same skills no matter which difficulty you hire them in, but at level x the stats of a merc hired in normal will be better than those of the same merc of level x hired in NM, and the NM merc will have higher stats than a Hell merc of level x. So for any act 1,3 or 5 merc, it's best to hire him in normal. Since the 1.11 patch you can hire mercs that are very close to your level, so it's very easy to swap.
It's different for Act 2 mercs though. Act 2 mercs have a special aura, but for a certain aura you have to hire them in a certain difficulty. Blessed Aim, Defiance and Prayer mercs can be hired in Normal or Hell; Holy Freeze, Might and Thorns mercs can only be hired in Nightmare. Just like the mercs from other acts, it's better to hire a BA/Def/Prayer merc in Normal because he will have a higher level aura and better stats than his Hell equivalent. HF/Might/Thorns mercs can only be hired in NM, so they will always have a little worse stats than Act 2 mercs hired in normal, but only they can provide those three auras, so there isn't another option. The usefulness of their auras (might and HF in particular) compensates their slightly lower stats though, so don't let that stop you
Edit: a small list of which mercs you can hire in which difficulty level
Act 1 Rogues
- Cold Arrow (Normal, NM, Hell)
- Fire Arrow (Normal, NM, Hell)
Act 2 Desert Warriors
- Defiance aura (Normal, Hell - "Defensive" merc)
- Prayer aura (Normal, Hell - "Combat" merc)
- Blessed Aim aura (Normal, Hell - "Offensive" merc)
- Holy Freeze aura (Nightmare, "Defensive" merc)
- Thorns aura (Nightmare, "Combat" merc)
- Might aura (Nightmare, "Offensive" merc)
Act 3 Iron Wolves
- Lightning (Normal, NM, Hell)
- Cold (Normal, NM, Hell)
- Fire (Normal, NM, Hell)
Act 5 Barbarians
- only one type here (Normal, NM, Hell)
For a full overview of the different mercenaries and some technical details, see
this.