FreeNepal,
It all depends on who is getting married. If it is between Nepali citizen to another Nepali citizen, its fairly easy. Get the "Sipharis letter" from your woda saying that your marriage is lagitimate and both couple have no existing previous marriage. Then go to CDO and fill out the application. That's it.
If the marriage is between Nepali citizen and international citizen, then this process can take as less as 1 month and who know how long. It will all depend on who do you know in Home Ministry,District Police Office, and Rastya Anusandhan Karyalaya. After finishing all this you go CDO again.
I have seen some people done it differently and avoiding this long process, but before you embark on any of the processes, ask American Embassy what kind of marriage certificate do they need? Will they be happy to have the one issued from the local juridictions like woda and Nagar Palika or it has to be from CDO. Getting this process done through local juridiction is much easier.
So, good luck.
SS