I think it took us about 18 months from starting the process to completing the five day assement and being accredited. We've not long had the first two day surveillance audit (one of two a year)
One of our directors was working on it for about 12 months, three days a week. He was overseeing it all and working through the S.O.A. and documenting what we do or identifying where we needed to make improvements. It shouldn't have taken quite that long, but that's another story.
I was doing much of the practical work from a PC and server side, and we had other engineers to do some of the networking work. Quite a few other people were involved for things like physical security on all the buildings, dealing with confidential waste paper and so on.
How much extra work that involves depends on how good you are in the first place. One thing that is a pain is all the record keeping that you have to do. It's not enough to do a particular task correctly. You also have to ensure that your procedures reflect what you do, and you also have to have the records to document that you have done it. There's quite a lot of things that you really need to audit and review periodically as well - every 6 months or yearly for example, and then document that it's all happened.
For a lot of the sections there's no single right answer covering what you must do, but you have to show that you have considered the risks and taken the appropriate actions to mitigate them for your business.
If there's any specific questions I'm quite happy to go through what we did in more detail.