I was in Australia rather recently, and was fortunate enough to do a ride along with QAS. The crew I was with said there were two Americans working in their particular division and gave me their contact details. One replied to me, and from what she outlined it is quite a taxing ordeal. Not impossible, but long and tedious. It took her a year and a half from turning in an application to first day on the job.
Fortunately, QAS will sponsor you for a
Skilled Migrant Visa - this is important because the fee for that visa is quite substantial. It's a step-by-step process though, and you don't need everything done straight away.
Start by downloading and completing an
employment application and sending it in. It takes at least 2 weeks for standard mail to get to Australia so keep that in mind.
Eventually, you'll have to decide whether or not you want to apply as an Advanced Care Paramedic (sort of like ILS but not really) or an Intensive Care Paramedic (ALS). Since you're a foreign applicant, you have to go through their RPL (recognition of prior learning) process. This looks to be rather daunting, as these evidence packets have to be completed:
Paramedic Level 3 (ACP)
Paramedic Level 4 (ICP)
In order to complete those packets you'll likely need to contact the program director for where you attended paramedic training and ask for the course outlines so you can appropriately document everything.
Hope that is helpful. Good luck!