My son is over in Afghanistan right now and I've learned tons from him. A good knife is priceless, but since they issue them a decent one I got him a Wilson COP tool because they're great for prying, chiseling, breaking windows, etc. The only thing he really felt like he needed was quality mags for his M4, I sent him a bunch of Magpul PMAGS and he's been happy with those. Other than those things, the best stuff has been books/novels, an ipod, and Copenhagen long cut.
He did take his laptop and he's made good use of it, mostly for keeping in touch and entertainment. He orders other things he neeeds/wants online and has it shipped right to him - bodybuilding supplements, boots, clothing, etc. They're pretty self-sufficient. Before he left I also gave a Bean digital camera, it's reasonably priced and pretty rugged, with a built in hook thing so he can hang it on his gear and take it with him and not lose it or have it get in the way.
It's crazy how much stuff they issue these days, they even gave him a high speed watch with a compass, altimeter, and all kinds of other things built into it.
Forget about guns, ammo, alcohol, and girly magazines.
They get in trouble for all that stuff. Well, maybe not the magaziines so much but they're on the forbidden list. You won't get in trouble but the recipient will.