Hey! That's a great idea - a guerilla gardening gift! In fact, I'll take it one step further - I'm really into what I term positive subversion (anything that thumbs your nose at society whilst doing good) so I'm into bookcrossing and freecycling ass well (bookcrossing: releasing registered books into the wild to be adopted by strangers, who might do you the courtesy of logging onto teh site and writing their comments; freecycling; giving stuff away for free that otherwise would choke up our landfull).
I might put together a basket-type gift wor everyone with a few seeds, a trowel and some gloves and maybe for those I like a lot o digital camera for documentation for the guerilla gardening, a bookcrossed book maybe on what grows best in the recipient's home area, and something freecycled: some pots or a rusty spade taken from council hard-waste cleanups etc.
What a great idea!