Show a wireframe, flat, and textured version of each map, include the poly count, and show some pics of the textures used. Video is probably the most appealing so try that, you can always use fraps to record in-game stuff and don't worry about the fraps.com thing on the top.
Still images (prints) are a good thing. They can be dished out quickly. Also, make a contact card with all of you information so they can get back to you.
Also display any other talents that support this. Employers like to see flexibility, and as well if you can be flexible with the fast paced technology now-a-days, you can move around in the job-place a little bit. This is very essential, and it makes you look good.
With your video, grab a really catchy song, believe it or not, you can be remembered for it.
ultimately, stay cool. Don't spaz out. That's noobish.