We were in Malaysia in June and got Celcom. Flew in KLIA and bought the sim after custom in the public waiting area. Cash only and they need your passport. The lady got everything set up for us which was really nice. There were other carrier booths like Hotlinks and Digi.
We paid about RM35 for the tourist Celcom sim and a 7-day data package. Spent 3 days in Melaka and the data speed was FAST! Much faster than the Verizon 4G we get here back home. We didn't make any calls and the data coverage was good in Melaka.