The following is all loosely based conjecture, and any PF people know about is welcome to inform me otherwise.
I would have to say years, at the least, considering the scope of physical, psychological, educational, and perhaps even spiritual training that you'd need to go through. What's more, you have to account for the implants and multiple surgeries required. That comes with testing and profiling, inpatient and outpatient therapy. Even when you factor in your first clone-death.
My best guess is that Capsuleer Program training starts early in the educational cycle. I'd guess it starts as soon as you're admitted to one of the twelve academies (assuming you passed the test to be admitted to said program). So let's say you enter [SWA] as a freshman, and you've passed the initial tests. Alongside your school studies, you'll now be subjected to more tests and your first bits of training.
Since Wetgrave and Mind Lock are notorious dangers associated with entering a Capsule, I would guess that all pilots are rigorously trained in mental control techniques, and possibly some spiritual or religious meditation techniques. Alongside, would be some healthy martial arts to help express that mental control through your body. Of course, military grade physical training would be included, to ensure you both have the stamina to survive the medical changes and have the utmost finesse in controlling your nervous system.
Book studies would be intense, learning various nuances about everything from Engineering, Electronics, Gunnery, Navigation, etc.... all those level 1 skills are probably trained the old fashioned way first.. or in whatever form a futuristic college would teach them. Extra studies specific for Capsuleers would be included, such as proper control of your pod, etc.
After that, you'd be given your first capsule and clone, after a long and grueling set of surgeries and implants to prepare you for your first brainscan. Then you die, and wake up in your first clone... which would probably take some recovery time, maybe even land you in a coma for a week or so if you didn't exactly do well with your training. You'll begin training with the actual capsule for a while, then finally you'll set up your contracts with PEND, CONCORD, SCC, Cloning Companies, and other authorities involved. This would be a major milestone in the process as your survival of that nearly guarantees your success of the entire program. While I wouldn't consider it the -end-, I would consider it your graduation. If you can't do this, you can't be a Capsuleer. If you can do it, you already are. You're just not ready to be on your own.
After all of that is completed, this is where we enter the game. Those of us who choose to complete our training will continue on with the game's OOC tutorial, and work out the Career Agents. This timeframe is roughly equivalent to the final weeks of your most senior year in the Academy. The Career Agent window provides those final weeks of direct training. This mostly relates to more of a Job Placement program in today's colleges.
All in all, my estimate of this is anywhere between 10-20 years of training. The Caldari State might train a Capsuleer in merely 7-10 years, thanks to their culture of total focus on the task at hand. I'd wager the Minmatar Republic/Gallente Federation may take around 10-15 years, with a focused regimen, though less so than the Caldari. Conversely, the Amarr Empire may take up to 20 due to... uhh.. I guess, more time spent in prayer and an outdated system of education and training.
Like I said, this is all conjecture. I don't have any PF to back this up.