You need a CNI from the British High commission, to prove you are unmarried.
First find a local notary for a statutory declaration, making a claim that you are single (unmarried) - 2 copies - 200MYR. Check with your local consular, because certain foreign citizens I'm told can obtain the CNI without the statutory declaration.
British High commission fees are 332 + 10 (for postage) MYR including courier. It's an awful place to visit regardless. You get stripped of your mobile phone going through security then you get to speak to local non-British staff through inches of bullet proof glass in a dire little waiting room.
Wait ~two working days for letter to be couriered. It's a shame the FCO can't do it then and there. If you miss the courier, you need to wait and collect from courier office the next day.
With the CNI letter in hand, you need to head to the Malaysian Foreign Affairs office (MFA) in Putrajaya to get it endorsed for 20MYR.
Warning: Strict dress code applies, no sleeveless tops. Putrajaya is about 45minutes out of Kuala Lumpur and you need to earmark an entire day to get stuff done here. This pathetic bureaucratic town which reminds me of Astana/Canberra has a massive roundabout with very poor signing.
The bureaucrat buildings themselves are large, however their waiting rooms are small and they seem to treat the public with contempt, so be warned and stay cool. Keep very low expectations.
After getting the letter endorsed, head to the National Registrar's Department (JPN) in Putrajaya. There are two KDN buildings and JPN is in one of them in Precinct 2. Since we are intending to get registered in a different local (in Kuala Lumpur) registrar's office, we had to get a permission letter to get married from JPN headquarters in Putrajaya, addressed to the local intended registrar's office. You can get registered in Putrajaya itself, so you can skip this step. However this means you have to return to Putrajaya to get married ... shudder.
With all these documents in hand:
Then we head to our local registrar's office in Sri Hartamas to put in notice of marriage. You can then set an appointment to register your marriage on applicable days between 21 days and upto 6 months. There is a minimum wait of 21 days after giving notice. They put notice on a pinboard in their office in the hope that members of the public will flag any impediment to your marriage. Silly that it is not online! The pictures are quite enjoyable. :)
Appear at the appointment with two witnesses above the age of 21. Everyone needs to bring identification. The fee is 30MYR. Enjoy the little signing ROM ceremony in a private room.
Finally don't forget to request an English version of the marriage certificate (10MYR) so that you can apply for EU visas and the such for your spouse.