I'm running a two-group campaign in which each group is playing in the same setting (thanks for Ptolus, Monte!). One group's beginning started out particularly well:
I had the homebrew fleshed out pretty extensively and the essentials of their home village mapped out (thanks for Great Rock, Andy Collins!), so what I had them do was generate characters with the essentials of the setting in mind. Once they had done that, I worked in secret elements of my own from the campaign into each of their individual backgrounds. They, of course, made it easy on me: 2 were playing bastards who didn't know their fathers, and one played an orphan.
I then met with each player individually to run a prelude (as youngsters before they fully became 1st level) in which I was able to a) provide them with a glimpse into the setting b) further establish their character within that context and c) foreshadow elements of the first full session.
Group:
Presici, a half-elf bastard child on her way to becoming a fighter, whose mother works as a "book keeper" for the inn. Elves are distrusted, so she has spent the better part of her childhood being picked on.
Devinus, a human bastard child on his way to becoming a bard, whose mother works at the same inn as a serving girl. He is like a brother to Precisi, and has made the "rounds" among the village girls.
Ichus, a human orphan training to become a druid under the care of a mysterious wisewoman outside of town. His only friends in town are Presici and Devinus.
Lyna, a rogue and relative newcomer to Great Rock, hails from the south. She left home to make her way in the world, fleeing the tragedy of a sister who mysteriously disappeared.
Basically, their preludes (except for Lyna's) center around the events of one night, in which a notorious group of mercenaries roll into town looking for a woman named "Sunia" (Devinus learned that it was his mother's name before she came to Great Rock) and her bastard child. During some of the dramatic encounters (in which Devinus lies his way out of capture, Precisi accidentally slays a young merc in a duel while trying to disarm him, Ichus accidentally helps the merc's 'warlock' find the location of a sinister abandoned temple near town), they learn a little more about the town.
The first session happened (in game time), a few weeks later when the mercs return with an infamous knight known for burning peasants alive. A mentor to the characters urges them to leave town (by now, they have figured out that the knight is probably looking for Devinus) by looking for a village boy whose gone missing--the bully who hassled Precisi in her prelude.
After some tracking, they find that the boys have gone into some sea caves--precisely where the hidden temple lay, as Ichus put two-and-two together.
Basically, all I had to do was to put some plot elements in the temple, and the campaign has almost run itself since then. They've been following up on leads within leads, and generating their own plot archs, as well as discovering all the ones I planted for them. Eight or nine months later, and about 9 levels later, many of the elements introduced in those preludes and first session are still affecting the game.
[EDIT: left out some vital info. DOH!]