If you are crafty, I suggest making beaded stitch markers. While getting all the supplies takes a little doing if you are starting from scratch, this is an unexpected, fairly easy-as-falling-off-a-log and useful gift.
There are tutorials on how to do it online...wait a sec, lemme go google it...here we go:
and the materials aren't that expensive. And I, a complete novice to beading/jewelry making, made a set of 6 during one World Series game, while talking on the phone with my sister.
round nose pliers,
side cutters (wire cutters)
bent needle nose pliers (though any needle nose pliers will do)
assorted beads (make sure they fit the head pins!)
and the O-ring part of a toogle clasp set
Michael's had a pretty decent set of the pliers and cutter for not too much money. Look thoroughly for the Toggle Clasps, because I couldn't find large numbers for cheap. Better Beads brand has a set of 6. Beads will cost however much you want to spend, but you'll generally have way more than you need. Same goes for head pins.
You may want to make one longer than the rest, to be a "beginning of round" marker.
Voila! Something unique, something pretty, something easy, something quick-to-make, something not too expensive, something useful (especially if they are into lace! and having more than one project on the needles at a time...) and something handmade.
What's not to like?