Go check out the announcement, and start thinking of cool talk ideas. Once you've got to that stage, be sure to read mbp's How to get a conference abstract accepted, and Mary's Getting a talk into linux.conf.au (not just because she's a co-chair of the paper committee).
This year, we've introduced one optional step: a video submission. If you think that you're a great speaker, and if only we could see you, we'd say yes instantly, then grab a camera, and convince us. :)
Also, if you're interested in running a mini-conf before the main conference, we're also taking proposals for mini-confs.
See you in Melbourne!