I review games for Game Tunnel, and usually I just get a download link, maybe a CD in the mail, but sometimes I get a full kit. Those kits make a huge impression on me, and I'm sure they do so for other reviewers and members of the media.
A simple and cheap folder with a business card affixed to it in some way, some papers with high quality screenshots of the game in question, a press release describing the new game and the company, and a CD with the game to review along with demos of all the other games the company has made seems to be effective. A strategy guide or hint book would also be a nice addition if you have one. I've received a packet like this from one company for a few games.
Another company sent me a CD, but they also sent me a spiral-bound packet about the game with high quality photos and quotes from the press, a postcard that sounded like it came from the game's universe, and I want to say a bumper sticker, but I am not sure. It wasn't as impressive as the folder mentioned above, but it was different.