Mobile phone service in South Korea is provided by three companies: KT Olleh, LG U+, and SK Telecom. Mobile virtual network operators (MVNOs) lease service from these Big Three.

You must be present in Korea for three days, before you are allowed to sign up for a phone contract. You can get around the 3-day limitation by buying a tourist sim.

Prepaid sim cards for tourists

You can buy a tourist sim card from the kiosks at the arrival halls of Incheon Airport and Gimpo Airport. You can get discounts pre-booking online. There are many different companies, but the most expat-friendly website and service is by Korea Telecom.

Korea Telecom (KT) tourist sims - Pre-book sim cards online for a 10% discount.
Evergreen Mobile - Buy at Incheon Airport, or select GS25 stores. Pricing varies in GS25 stores, and is more expensive than buying directly from Evergreen Mobile. The reload system isn't straightforward - you must add credit to your account, and then shift it to a data sub-account. You must also email them your phone's MAC address in order to use their wifi network, and wait for someone to manually add it to the system.

Long-term sim cards

KT Olleh

KT Olleh is probably the best English-language service. They have an English-language customer service line, which you can view here: http://www.kt.com/eng/
KT Olleh maintains an English website at global.olleh.com, but it is mostly for home telephone/TV/internet service, and does not include mobile phone networks. The website only provides information, and does not allow for purchases or reservations.
There are several Global Stores that cater to expats. There are no Global Stores in Incheon, but the closest English-speaking Global Store is in Hongdae.
olleh membership is their customer loyalty card system. You gain a certain amount of points per month, and can swipe your card at various retailers for immediate discounts. These discounts are deducted from your points. You can sign up for the card at an Olleh store, or sign up online for the plastic card (it will be mailed to you). You can also sign up and get the card's barcode immediately by using the Olleh Membership app (Google Play / iTunes App Store), or the MoCa Wallet.

LG U+

English informational site.
Similar to USA's Verizon Mobile. LG U+ phones are locked to a specific wavelength that is not used outside of South Korea. If you plan on using your phone outside of Korea, you probably do not want to sign up with LG U+. LG U+ phones can only be used on the LG U+ network.