Melbourne's Tullamarine airport has flights to all Australian state capitals and regional Victoria. The major domestic carriers are Qantas and Ansett. Always ask for special deals or discount fares. These are more likely available if you book and pay one week or preferably two weeks in advance. Two new discount operators fly limited routes.
Impulse flies from Melbourne to Sydney and onto Brisbane.
Airline discounts are greatest if booked on the internet. Many international flights come and go from Melbourne airport.