Caveat - I'm not a geographer, and only a hobby mapper, though I once worked in the hardware & systems end of a GIS outfit (Intergraph). But my bets would be to show you're into GIS, not just a competent mechanic. Contribute to openstreetmap.com, do something interesting and useful through the GoogleMaps API. Build a portfolio, particularly of material you honestly got PAID for -- even if it's small amounts. Tailor your portfolio each time you present it, to match the needs of the recipient - geological maps if an oil company, demographic and civil engineering related stuff if you're talking to a city mapping department.
If you have subject-matter interests and abilities outside of GIS per se, MILK them. Music? Put together something showing where certain styles or instruments are, or show the spatial distribution of the development of an instrument type. Transport? Tackle a real-life road, street, railroad subject. If it's history, put together something *period* in a historical style, AND something maybe in a history-text vein. Everybody's taken history courses - if you have done something that could have been published in textbook or reference book, maybe you can "borrow" the cachet of that from an interviewer's memory. Careful - an acquaintance was being interviewed for a clearance at work, and had put down her beloved history professor as a reference.... turns out the prof had once flunked the investigator in a university history course. So maybe you want the aura of academia only in certain situations :-)...
Show you can handle a variety of tools - lay your hands on as many student-discount, demo, or borrowed professional GIS apps, and at least get to know a bit about them. Your goal there though might be more to show what you can learn, than what you already know. Yeah, there'll be job postings demanding years of experience in ArcGIS or whatnot.... your goal will be to circumvent the Human Resources hack whose job is to eliminate non-matching candidates, and instead wrangle a visit with the people who really need the work done. THEM you can probably convince you "speak fluent map" and they may acknowlege the different software is all just implementation of GIS principles.
Anything you show off in a portfolio, edit and edit again. Get others to proofread, and follow advice. Be scrupulous about use of paid vs. open-source fonts, etc, even to the extent of listing what you use.
Purge Facebook and any other online forum of anything the least bit unprofessional - employers DO mercilessly check up on you. Conversely, it may be too late to plant a long-term view of yourself in noticable places, but it can't hurt to be visible online in a courteous, helpful way. Ask intelligent questions that show you've first done your homework, offer the benefit of your experience if you really have some :-). Look into LinkedIn for contacts - it takes a while to build a network, but it lets you make use of other folks' networks. This'll be particularly useful if you know GIS graduates from the last couple of years at work already.
It's probably important to remember your goal is to get work SOMEwhere, even if not a dream job. It's theoretically easier to GET work if you already HAVE work :-). Conversely, figure out just what IS your dream job, and go out and hunt it down ruthlessly. You do want to work at something you enjoy, not at some soul-sucking toilsome grind. Just don't be afraid to do some grinding up front - you're after all getting an entry-level spot. Don't give up even in a crummy market; SOMEbody needs the very best possible workers - be one and there's a spot for you out there somewhere.
Get a copy of What Color Is Your Parachute? and don't just read it, but do the exercises. You may be surprised at angles on a possible career that you hadn't thought of.
And be tolerant of long-winded advisors. Like me ;-)....