Hi there
You will need to get your skills assessed by the Australasian Podiatry Council, and also register in the state(s) in which you wish to work.
You have several visa options, including Working Holiday Visa - which is likely the cheapest and quickest option. There are pros and cons of all visas, it's just a question of working out which is likely to offer you what you want. The following websites will give you some info about visas in general:
www.immi.gov.au &
www.pomsinoz.com (this latter is a forum, which I've certainly found helpful during my visa application).
Hope this helps a bit!
Sarah