tominated, there are plenty of inexpensive name providers out there, but here are a few pointers for you.
Some of them will require that you tack your names onto theirs, meaning that you can't move your site if you get disastified with them as they own the base domain (for example tominated.myispservice.com).
If you go with the other way and use, for example tominated.com, most providers will register that name for you, possibly for a small fee, or bundled into their services. If for some reason you become unhappy with them, you can move the name, but then you will sometimes find yourself immersed in confusing operations authorizing the move, and possibly down for a while. Also, the new provider may want a small fee (yet again) to process the change of the name move.
The last option is to register your chosen name with a top level registrar yourself. That will probably cost a little more because the above mentioned providers are able to purchase bulk services and pass on the discount to their customers. But this gives you the capability of controlling your name server pointers once you decide on a provider - this time just for hosting services. Then if you ever want to move, sign up with a new provider, get your web site set up there, change the names servers with the registrar, delete the old site and say goodbye to them.
I use network solutions for my domain registrations, but you being in the down under, you may have some other registrars available. I hope this is clearly spelled out, and if you have questions, please give a shout. All said, understand that there is a difference between registrars and hosting providers, in most cases.