Most places are not going to really consider your application until you are licensed/certified in that state. You should be able to find reciprocity information on each state's EMS office website. Usually the process can be done through the mail and depending on the state may not even be that expensive.
It's different for each state. Many agencies require you have or are "able to obtain" certification in the state. In some cases that means you'll be hired and your paperwork will be submitted to the state. In other cases, like Colorado, you must apply for the cert first. It's worth a call to the agency you're applying with to suss out the certification process for each department.