I really liked the Red Hat Certified Engineer program. David is right in that it costs a lot. I had been saving for months before I figured out a way to have work pay for it. Will it get you a job? I can't say for certain, however, go to monster or dice and do a job search for Linux then filter out all the ones asking for RHCE. The difference is huge (one of the reasons why I started studying on my own). This is not an easy test. Be prepared. The new book by Micheal Jang is rather heavy but a great reference book. I don't agree with his method 100% but I do think it would prepare you for the RHCE. The test by itself is far cheaper then the class and test.
There are plenty of other certifications out there too. I have heard good things about the Canonical Ubuntu certs. I do not have them though.
If you are focusing on security I know a few people who have done the
http://www.metasploit.com/ testing. They said it was really good. In fact they all have jobs doing penetration testing now.
Also, keep your eye out on
http://www.damnvulnerablelinux.org/ .The last version is kinda dated now, but they had a BUNCH of training, tutorials, and tests that you could learn security from. I know they are working hard on the next version. If you really are serious about learning, it would be a HUGE help to the guys if you could get a pre-release and go through all the tutorials with a write up. If you could document the process from the eyes of a newbie you might uncover bugs and things that could help them improve the process before they do a final release. I thought about doing a blog and working through a tutorial per post documenting my findings, but I have been super swamped recently. Anyway, I have heard great things about DVL in the past and I went through a few of their tutorials on Apache vulnerabilities that I was able to fix in my own servers. Worth checking out. They are expected to make a release in the next month or so, if you have any desire to help test it out, now is the time.
Hope that helps.
~Stack~
RHCE