I would like to give a plane ticket from Perth to Melbourne (Australia) as a gift. However, since it is a surprise, I do not know the dates. How can I do this?
Give money instead of a ticket and the receiver could buy the ticket themselves. The advantage is that the receiver may choose additional booking details (e.g luggage, leg room). The disadvantage is that the receiver has to spend time booking the ticket or (as @phoog noted) the person may misuse the money;
Give a gift voucher. For example Virgin Australia has them as it is written on their website. This resolves the issues with misusing the money preserving ability to choose additional options, however, you fix the carrier, so it may cost more than the cheapest option.
Buy a fully flexible ticket, so that the receiver can change the date. For example, Virgin Australia has such tickets (according to their website):
Flights booked via our website, mobile website or downloadable mobile application can be changed online or via the application up to 60 minutes prior to scheduled departure; or via the GCC up to flight departure. No change fee is applicable. Any difference in price between the original and new fare must be paid.
However, in this case the price is higher than economy tickets.
Are you buying them any ticket they want or have you a budget in mind?
You could always just give them a card with nice penmanship saying you are giving them a ticket from X to Y on the date of their choice. Of course a handwritten card maybe way too old fashion for this crowd.