While some employers say they require certification, the majority don't really care.
Let's face it, a certification is simply another test that you have to pass, and as with any tests, there are "study guides" available which will coach you into passing the exam, but not really knowing the material.
This is fairly prevalent in the Microsoft ecosystem, where plenty of MCSA, MCthis, MCthat simply don't know how things really work. This phenomenon is not unique to Microsoft, the same could be said for Cisco, Oracle, IBM, etc... Of course, in the MS world, certs make a certain amount of sense, as the primary vendor controls the curriculum.
I can't speak to the Linux certifications, but it appears to be more fragmented. The Linux Cert FAQ lists 4 certification programs: CompTIA, LPI, Novell and RedHat. This represents quite a bit of fragmentation. There is no guarantee that whichever certification you have is the one the potential employer would be looking for.
Since you are in the Linux side of thing, you should be able to do plenty of self-study, as the software investment costs are close to nothing.
A good book on system administration would probably be a good investment. I personally recommend Essential System Administration by Frisch, but others swear by the "red book" (sorry, the name escapes me).
As an employer, I would choose someone with curiosity and a bit of acquired knowledge over someone with letters after their name... all things being equal.