I had a whole post typed up about teaching yourself, but I guess security research in academia is starting to grow up. See CAE-R schools at http://www.nsa.gov/ia/academic_outreach/nat_cae/institutions.shtml. You'll want to look at potential schools a lot more closely, but that list is a good place to start.
A job with a company like Cisco or Microsoft or in the banking industry would be a good place to get some experience if academia isn't where you want to be. You'll still need to self-train to be competitive for security consultant type jobs. You may want to get involved in a security related open source project, and definitely try to get some network administration experience on your resume.
If you end up with a company that will support further training, do what you can to work toward a CCSP / CCIE Security certification from Cisco (
http://www.cisco.com/web/learning/le3/learning_career_certifications_and_learning_paths_home.html) if some other path doesn't become evident.