Mercenaries are at Bowerstone South, Twinblades Camp, Oakvale, and the Temple of Avo. They will teleport with you, and in the original Fable, once they are dead, are gone forever.
Sacrifice them at midnight if you are trying to get Skorm's Bow. You can tell it's midnight by looking at the in-game sundial on the HUD. It is midnight when night covers the top half, and the arrow is pointing to the dead center of the night section. Also, mercenaries get paid every hour on the hour, so the *chink* of the payment is a good indicator to help you out.
Time...Line? Time isn't made of lines! It is made of circles. That is why clocks are round. - Caboose