I will agree with the beer, but make that a freebie and tell him it's form all of us, as a huge THANK YOU for signing up and serving our country.
Really, do pass along a THANK YOU form a stranger, for me.
As what to get, I'm a Victorinox whore, I must have 10 Victorinox knives, the only problem I have with my SwissTool is NO SCISSORS!
In the Army we had to take care of our uniforms, even in the field, and scissors are a life saver, every thing a single blade can not do scissors can in the field.
Get it engraved for him too, (so a standard Victorinox is out with it's plastic scales) may cost 10$ extra, but I'd treasure a knife from a buddy that took the time to come to graduation and see me. The tool that comes to mind here is the Leatherman Wave, it's SS so it will take the abuse, can be engraved, it has a saw (another high point in the field) and (what else) Scissors!
sorry if i rambled.
RTFM