heh, yeah - they mean some paper from a university i think. CCNA is good, but experience definately is the main killer.
for example, check out
http://www.reed.co.uk. Do a quick search using CCNA as a search term when you're in the IT -> Systems/Network Admin section and count how many times you find something along the lines of:
"2years hand-on Cisco experience up to CCNA Level. Knowledge of Cisco VPN Concentrator, Cisco Switching, Cisco Routers, Cisco Pix Firewall, Cisco Secure, Good understanding of MPLS, BGP, HSRP, VPN, DSL, and TCP/IP
Good Cisco troubleshooting skills encompassing a general level of knowledge of Microsoft networking and PC configurations"
Bits of paper are good, but experience is better - I know plenty of highly skilled people with loads of experience but no qualifications, simply because they've never been bothered to do them. It doesn't matter though - they could easily out-perform some people who are certified up to the eyeballs.
Unfortunately its a no-win situation though - you can't get experience without a job, and you can't get a job without experience. You may have to start with a less-than-ideal job in order to get the experience to allow you to start applying for better jobs.