I have been hiring nearly constantly for about 10 years. 6 years hiring Solaris guys, and the last 4 hiring Linux guys. I will be the first to say that around Philadelphia anyway, the market is full of dog shit I wouldn't pay $40k. So if you want a job, figure out a way to shine brighter than everyone else. Some ideas:
-Intelligence cannot be faked, but also cannot be earned, unfortunately.
-Use spell check on your resume, have someone else read it, ugh! If you've been around the block 20 times, limit resume to 2-3 pages or it gets trashed.
-Groom yourself, even for a startup interview. Nobody likes smelly, sweaty, people in grungy clothes.
-Do whatever you have to do to NOT be/appear nervous in the interview. Relax--we're trying to get to know you, the real you!
-Do NOT put stuff on your resume that you do not know!!!! Or at least qualify your knowledge (e.g. "I am vaguely familiar with VMware")
-Learn how to shake a hand and hold eye contact (yeah yeah, tricky for some IT folks)
-For a Linux admin, you'd better have the basics down pat (resolve.conf, named.conf, ntp.conf, httpd,conf, how to change a system IP/hostname, how to add a new filesystem, how to rescue a system that won't boot, or you forgot root pass, etc etc etc)
I will say, I have learned my lesson about hiring young people without a degree. A degree shows you can think 4+ years ahead to a goal, and work hard to get there. If you don't have a degree, have a good reason why, and let them know why you can follow through on things.