There are three ways to increase skill levels on a Merc.
The first is generic "+all skills". Some examples would include the +2 Skills from a Spirit sword/shield, or the +4 skills from Arioc's Needle.
The second is +to a specific skill. If you give an A3 Lightning Merc a Charged Bolt Ormus' Robe, that would increase his level of Charged Bolt by +3.
The third is +fire skills (found on Hexfire), which will increase the skill levels of an A3 Fire merc.
+Paladin skills, +Sorceress skills, +amazon skills, +barb skills, +combat skills, +offensive auras, +lightning skills... none of these will work. Only the three above methods will increase a merc's skill level.