Do I need to speak Malay to travel in Malaysia?

No. Most Malaysians speak good English, especially in cities, hotels, malls and tourist places. A few Malay words and a friendly greeting are still very much appreciated.

Is Malay easy to learn?

Malay is one of the easier languages for English speakers. It uses the Roman alphabet, is spelled as it sounds, and has no tenses, genders or verb endings.

What greeting should a Muslim visitor use?

Say "Assalamualaikum" and the reply is "Waalaikumussalam". Anyone can also use "Selamat pagi" (good morning), "Apa khabar?" (how are you?) and "Terima kasih" (thank you).

Malay Phrasebook for Muslim Travellers: Everyday Words and Arabic Expressions Used in Malaysia

Malay (Bahasa Melayu) is written in the same Roman alphabet as English, so you can read every word below aloud. Most Malaysians also speak good English, but a few words of Malay, and the Arabic expressions that Malay Muslims use every day, are warmly appreciated. Spellings can vary a little between regions.

Arabic expressions used every day

Assalamualaikum: Peace be upon you (the standard greeting, any time of day)
Waalaikumussalam: And upon you be peace (the reply)
Alhamdulillah: Praise be to God (thanks, or "I'm fine")
InsyaAllah: If God wills (said about plans)
MasyaAllah: God has willed it (admiring something good)
Subhanallah: Glory be to God (amazement)
Bismillah: In the name of God (before eating or starting something)
Astaghfirullah: I seek God's forgiveness (after a mistake or a shock)
Jazakallah: May God reward you (a formal thank you)
Allahuakbar: God is the Greatest
Salam: Greetings (a short hello)
Amin: Amen (after a prayer or a good wish)

Arabic words that became Malay

Halal / haram: Permitted / forbidden
Masjid: Mosque
Surau: Small prayer room
Solat: The five daily prayers
Azan: Call to prayer
Wuduk: Ablution before prayer
Doa: Prayer or supplication
Adab: Manners and etiquette
Rezeki: Blessing or livelihood
Sabar: Patient
Syukur: Gratitude
Puasa: Fasting
Sedekah: Voluntary charity
Ustaz / ustazah: Religious teacher (male / female)

Greetings and politeness

Selamat pagi / petang / malam: Good morning / afternoon / evening
Apa khabar?: How are you?
Khabar baik: I'm fine
Terima kasih: Thank you
Sama-sama: You're welcome
Tolong: Please (asking for help)
Maaf: Sorry
Tak apa: It's okay, never mind
Jumpa lagi: See you again
Selamat tinggal: Goodbye

Basics

Ya / Tidak: Yes / No
Boleh: Can, or okay
Tak boleh: Cannot
Saya / awak: I / you
Nama saya…: My name is…
Saya tak faham: I don't understand
Boleh cakap Inggeris?: Can you speak English?

Getting around

Di mana…?: Where is…?
Berapa?: How much?
Murah sikit?: A bit cheaper?
Kiri / kanan / lurus: Left / right / straight
Berhenti sini: Stop here
Tandas: Toilet
Masjid di mana?: Where is the mosque?
Arah kiblat: Direction of Mecca (qibla)
Lapangan terbang: Airport

Food and drink

Makan / minum: Eat / drink
Air kosong: Plain water
Sedap: Delicious
Pedas / tak pedas: Spicy / not spicy
Halal ke?: Is it halal?
Tambah nasi: More rice, please
Bungkus: Takeaway
Bil: The bill

Numbers, pronunciation and tips

Numbers: 1 satu, 2 dua, 3 tiga, 4 empat, 5 lima, 6 enam, 7 tujuh, 8 lapan, 9 sembilan, 10 sepuluh.
Pronunciation: Malay is spelled as it sounds. The letter c is read "ch" (cantik sounds like chantik) and a final k is soft.
No tenses: Malay words do not change for past or future. "Saya makan" can mean I eat, I ate or I am eating. Add "semalam" (yesterday) or "esok" (tomorrow) if it matters.
Plurals: Say the word twice: buku is book, buku-buku is books.
Greeting etiquette: Many Muslims do not shake hands with the opposite sex. Wait for the other person to offer a hand, or place your right hand over your heart and nod.
Mixing English is fine: Malaysians often mix English into Malay, so a few English words in your sentence are normal.