Personally I always travel with a bag of Clip-on Koalas!
These make a great gift to give out along the way as they are both a great representation of my home country, as well as being suitably "cute" - plus they are cheap enough to be able to give out without concerns for the cost. Recently I've even started leaving them in hotel rooms when I checkout (clipped to a light or the fridge, or somewhere else that I know the maid will find it).
So far I've had two "sightings" of Koalas that I'd given out/left previously - one clipped to the maid cart in a hotel I had stayed in a few weeks earlier, and a second on the bag of a flight attendant as she was walking through an airport (and she even remembered me when I asked - I'd given it to her about a month earlier)
I also sometimes travel with a few small boxes of chocolates (Like these - 4 chocolates and about $1 each at my local supermarket). It's amazing the impact giving one of these to someone as a "thank you" can have during a trip - both on the person you give it to, but also on yourself for being able to actually thank someone that has made a trip more enjoyable for you!