I have bought an iPhone 5s from USA, and sent it back home, however it shows "SIM Not Valid". Is it factory locked, country locked or something else? How can I fix it?
Depending on which model you bought in the US, you may or may not have a sim in the phone.
Sounds as though you have a sim, you will need to remove the US sim, buy a sim from a provider in the country where you are going to use it (or enable roaming - although it does not sound as if you are having a roaming issue).
You noted in your comments that you used other sims, if so then:
YES, your phone is most probably locked to a US carrier.
To answer your question how to fix it. You need to buy a non carrier locked phone from Apple in the US, or jail break your phone.
This site does not condone jail breaking however I can point you to a very good site called google which will help you out.