I started this thread many months ago. Now that I've actually moved and brought my pet along with me, I've decided to update this thread with the relevant details. Note that all this applies to bringing a dog from Sabah to West Malaysia. The following are what you will need:

1. You will need an Import Permit from Kuala Lumpur. In my case, I went to the Department of Veterinary Services at 4, Jalan Selar, Taman Pertama, 56100 KL. You will need to fill out a form and pay a modest fee, like RM10 or something. In my case, they also asked for photos of my dog standing up, front and side view. Note that the permit is one-use only and you must import the animal within 30 days of the issuing date of the permit so you can't apply for it too far in advance. You will not get the permit in one day. You'll have to submit the application and come back for it once it is ready.

2. Once you have the Import Permit, you need to apply for an Export Permit from Sabah. Luckily you can begin the process online as the Department of Veterinary Services of Sabah has an online portal for this purpose:

http://www.davetsa.sabah.gov.my/app/

You will need the number of the Import Permit from KL and fax them a copy of it and you will need to fill out all of the relevant information. Once it has been processed, they will ask you to go to their offices at Wisma Pertanian, Kota Kinabalu to pay the fee of RM5. Then you go home and once again wait for them to call you to come collect it when it is ready.

3. Finally, you need a Health Certificate for your animal from the Department of Veterinary Services. I went to the offices at Kepayan, Kota Kinabalu. I also bought a microchip for my dog and had it injected at this time. Then you pay the fee of RM30 and once again wait for them to call you to pick up the certificate when it is ready.

4. We traveled on MAS and treated our dog including her cage as check-in luggage. The usual rate is RM15 per kg. Apparently MAS Kargo can do it for slightly cheaper but the procedures are different and we had a hard time getting consistent information from MAS, so we opted just to do it the simpler way. They allowed us to count the weight against the usual luggage allowance of 20 kgs and charge us only the excess. However we were earlier told that we would need to pay the full amount for the recorded weight for live animals. That's just MAS being inconsistent again so I have no idea what the correct way is. We weighed all our stuff at the normal check-in counter and then took our dog in the cage to the oversized luggage counter.

5. Once we arrived at KLIA, the quarantine officer collected all three documents and kept the original copies of all of them, so if you want to keep a photocopy of them in case there is any problem you should do it beforehand. I was also asked to pay RM40. I don't know what that was for but I did get a receipt for it. The quarantine officer also verified the microchip's registration number against the number stated in the permits.

I hope this account will be useful to whoever needs to do something similar. Overall it wasn't as expensive as I feared but it was very troublesome as you need to visit multiple offices and you can't get your documents in just one visit.

Importing To East Malaysia (Sabah and Sarawak) 

Let me begin by saying that information on importing into East Malaysia - Sarawak in particular - is more difficult to find.  Those wishing to bring pets into Sarawak may need to visit the state's veterinary services department or employ an agent to help. 

PetRelocation.com has some information about E. Malaysian policies on their web site: http://blog.petrelocation.com/blog/pet-travel-advice/moving-pets-to-malaysia-importing-pets-to-sabah-and-sarawak

 
The following 2010 blog entry contains a very informative first-hand account of importing cats into Sarawak. It includes the official policies regarding import from other countries and West Malaysia, including specific information about quarantine periods.

https://september152010.wordpress.com/tag/pet-import-to-sarawak/

The following article originally appeared in The Star in 2010. It includes some good information about importing pets into both East Malaysian states, as well as some excellent pointers about the timing of vaccinations.

http://www.thestar.com.my/metro/story.asp?file=/2010/10/23/sarawak/7281283

From PetFinder.my forum members' posts, it seems that Sabah is slightly more relaxed about quarantine than Sarawak. Some members have reported that Sabahan officials occasionally agree to 'home quarantine' if the owners can guarantee that the animal will be kept safely isolated.  You can apply for your import permit to Sabah on-line by creating an account on the state's  Veterinary Services web site.

As for transport, MAS is the only airline permitted to transport pets from West Malaysia to Sarawak

Importing To Indonesia

The guidelines for bringing pets into Indonesia depend upon the originating country, and whether or not that country is designated "rabies-free".  These designations change from time to time, but at present, Sarawak and Sabah are deemed rabies-free, and West Malaysia as having no reported cases within the past two years. As such, all animals traveling from Malaysia (East or West) will, provided all their vaccination records are in order, be allowed into Indonesia.  All animals are required to spend a minimum of 14 days in quarantine on Java.

Those bringing pets into Indonesia are advised to fly them first into Jakarta, on Java. They should then be aware that other Indonesian islands, such as Bali and Sumatra, may have additional or different requirements.

The following web page, designed for expats with pets, offers very comprehensive information, including tips for helping pets adjust to life in Indonesia and links to official government web sites:

http://www.expat.or.id/info/pets.html

Importing To Singapore 

Singapore, being a rabies-free island nation, also has stringent pet import policies.  Import licenses are 50SGD per pet.  The minimum quarantine period is 30 days, and reservations at the quarantine station are required. 

The following is the Agri-Food and Veterinary guidelines for importing pets to Singapore:

http://www.ava.gov.sg/AnimalsPetSector/ImportExportTransOfAnimalRelatedPrd/PetsPersonal/

The web-site includes a link to a very handy "calculator" - a tool to lay out the specific requirements and time-lines, based upon the country from which your pet will be arriving. 

Importing To Australia 

Australia is perhaps one of the most complicated and expensive destinations for pets coming from Malaysia.  Pet owners who have all their documentation in order can import their dogs and cats into Australia with a minimum of one month's quarantine, but be warned - as one PetFinder.my forum member put it, "Do not expect any compassion or leniency. Believe them when they say they will send the animal back to Malaysia at your cost if things are not done correctly."  

I would suggest that readers start at the Australian Government's own web page on importing animals and the quarantine requirements.  

As Malaysia falls into the category 4 countries "in which rabies is absent or well-controlled", the list of specific requirements for Malaysian pets is here.

Note that some of the blood tests must be done at specific laboratories, many of which are outside Malaysia, and many must be done within a certain time-frame to minimise the animal's quarantine period.  For example, the Rabies Neutralising Antibody Titre Test (RNATT) must be performed at an approved testing facility. If the blood is tested more than 150 days before the animal arrives in Australia, the quarantine period is 30 days.  If, on the other hand, the rabies test is only 60 days before arrival, the animal faces 120 days in quarantine. It pays to plan far ahead! 
 

Here are some accounts of first-hand experiences from PetFinder.my members who have brought pets to Australia.  They range from general estimates of cost to very specific information about blood testing.