Hi,
unlocking a phone for use with other carriers isn't illegal as far as I know, certainly not in the UK/US, wikipedia seems to think there are no laws in Australia either so I think you're safe.
Usually you can get the code from the operator that the phone is locked to, especially if it's a phone with a monthly contract and that contract has expired. It's worth giving them a call to see if they'll give it to you for free.
Failing that there are hundreds of sites that will, for a charge, take the IMEI number you send (which you can usually get by typing *#06# into the phone then pressing call) and return you the unlock code for your phone. They should also provide instructions on how to enter this code.
HTH
Nick