Jumping into security relatively cold -- as it sounds like may be the case for you, given your prior lack of on-the-job infosec experience -- essentially means starting from scratch. Thus, you'd probably want to start out with the SANS GSEC or the CompTIA Security+, and then pursue a strong mid-level cert in the SANS GIAC program or perhaps go after the CISSP (you can take and pass the exam and become an ISC-squared "associate" before you meet the experience requirements and get to call yourself a full-fledged CISSP, which requires four years of infosec on-the-job experience at a minimum).
It will take you at least a year to get started, and as long as four years to gain journeyman status as an infosec professional. In the meantime, you should ponder the fact that over half the people who go on to become full-time security professionals come from the ranks of system and network administrators (who represent the front-line troops in the security arena anyway). Thus, you might want to consider pursuing Microsoft or Linux administrator credentials (MSCA/MCSE or the TS/ITP programs that will replace them on the Microsoft side, or perhaps the LPIC, Novell CLE, or Red Hat credentials on the Linux side of the street) as a stepping stone into the security field.
Another potential path of entry -- albeit more time-consuming and expensive -- would be to pursue a Master's degree in computer science or engineering with an infosec focus. The National Security Agency has identified a series of schools as National Centers of Academic Excellence in Information Assurance Education (CAEIAE), most of which offer programs that also provide great ways to get involved in the field.
HTH and thanks for posting. Best of luck with your career planning and path!
This was first published in January 2006