Factory unlocked iPhones come unlocked, and therefore do not require you to unlock it yourself. However, they are far more expensive then buying locked iPhoens and unlocking them on your own.
You need to jailbreak in order to unlock, sorry.
You'll still be able to use the app store even though you've jailbroken.
To unlock, you need a jailbroken phone, so yours is def jailbroken. Redsn0w jailbreak your iPhone (any version), Boot Neuter can be downloaded from Cydia (or maybe redsn0w does this?) for original iPhone's. The 3G and 3GS need to have ultrasn0w used after redsn0w to unlock the device.
Ok... And so if i unlock it, its not permanent? I'd have to rejailbreak after each update? Sorry for all the questions, im just trying to make sure i understand the situation.
I could be wrong but i seem so remember someone saying that once a phone is unlocked, it stays that way?