There are 2 alternatives to get to Malang by plane. The first option is to go directly to Malang while the second option is to enter via Surabaya, which has several direct flights from Singapore, Malaysia, as well as many other cites in Indonesia. From Surabaya, you could take train or bus.
Direct to Malang (Abdul Rachman Saleh Airport, MLG)
Abdul Rachman Saleh Airport is served by daily flights from Jakarta which are operated by Garuda, Sriwijaya, Batavia and Lion Air, as well as by daily flights from Denpasar which are operated by Lion Air. The airport is located at the east of the city, and a cheap and easy taxi ride from your hotel in Malang. Shoestringers also have the option of traveling by mikrolet (public minibus).
Via Surabaya (Juanda Airport, SUB)
Surabaya is the second busiest airport in Indonesia, with frequent daily flights to Jakarta and many other destinations within Indonesia. In addition, there are also direct international flights to Surabaya from Singapore (AirAsia, SilkAir, China Airlines), Kuala Lumpur (AirAsia), Penang (AirAsia), Bandar Seri Begawan (Royal Brunei), Bangkok (AirAsia), Hong Kong (Cathay Pacific, Garuda), Taipei (China Airlines), and possibly other locations.
For the late arrivals, there are lots of hotels right near the airport; until about 22:00 hours there is a hotel booking office at the airport that will find you a room; after that, just hire a taxi and ask them to find you a nearby hotel in your price range.
Getting to Malang from Juanda Airport (Surabaya)
The easiest way to go is by taxi, directly from the airport to your hotel in Malang; typical travel time is about 2 - 3 hours, though it can end up either less or more, depending on traffic conditions. Official taxis, which are comfortable and presumably more reliable, go for a fixed price of IDR 436,000. Alternatively, if you're so inclined, you can knock a bit off the price by bargaining with one of the touts.
A mid-range option is to go by "travel", which is a minibus with about 6-8 reasonably comfortable seats, at IDR 70,000 per person. They leave the airport when full, and drop each passenger off at his or her destination, so it's like a taxi, except that you have a potential wait before departing, and a potential lengthy free tour of Malang suburbia at the other end if you're (un)lucky enough to be dropped off last. Finally, budget travellers can catch the Damri bus from the airport to the Sidoarjo Bus Terminal, from which buses are available to Malang.
An important thing to note is that Surabaya airport is located at the south of the city on the road to Malang, so unless you have some particular reason to visit Surabaya, there is no reason to go into town first in order to get to Malang.
It is also possible to travel to Malang by train from various locations in Java. In addition to a variety of slow economy class trains, there is also an overnight train, the Gajayana, with business and executive class services from Jakarta to Malang, stopping at Purwokerto, Yogyakarta, Solo, Madiun, Kediri, Tulungagung and Blitar. The journey from Jakarta takes 15:30 hours, and is an excellent option for those traveling from Central Java especially.
Frequent buses run from most cities in Java to the Arjosari Bus Terminal in Malang. Many of them go through the Bungurasih Terminal in Surabaya. Direct buses are available from Surakarta, Yogyakarta and Jakarta. There are a variety of options, ranging from local, non-air-conditioned buses which make frequent stops, to “Patas” bus, which are air-conditioned and run between the major cities only