The ones I've used in the past:
Other PCs were hired by Party Leader
PCs were all hired by a particular NPC to fulfill a particular task
PCs were childhood friends/from the same town.
PCs worked together in some organization (military, mercenary band, robber band, religous order, guild, whatever), and were assigned to the same mission.
PCs were all wrongfully imprisoned and escaped together.
PCs were part of a caravan that was ambushed, and were the sole survivors, and had to make it to civilization.
And the old cliched everyone meets in a bar.
Of those, I have to say that the prison-break was my favorite, but I don't want to overuse it either. But I really dislike having a party that has no logical reason to be together, no cohesion, and no party loyalty. Anyone have any good methods for why the party knows each other and adventures together that you've used in the past?