The nationals of 109 countries and territories, including all the usual suspects, will receive a visa on arrival valid for 30 to 90 days; see the official Hi Korea site (http://www.hikorea.go.kr/...) for the latest details. Rules for visiting only Jeju are even more lenient, allowing in everybody except citizens of 11 countries. Don't overstay, even by a single day — this incurs heavy fines and possible jail time, and you'll probably be banned from re-entering.
Military personnel travelling under the SOFA for South Korea are not required to possess a passport for entry, provided they hold a copy of their travel orders and a military ID. On the other hand, dependents must hold a passport and A-3 visa for entry.
Due both to its location at the end of the Korean peninsula and the political situation with North Korea, entering South Korea overland is practically not possible. The border between North and South Korea is considered the most heavily fortified border in the world, and while some crossings have occurred at the truce village of Panmunjeom, one of the cases a Soviet defector in 1984 was shot at by both sides and, although he survived, you might not be so lucky. In the 80's and the early 90's most of those who crossed the border either way would be arrested and prosecuted for reasons mostly referred to as 'threatening national security'.
Busan Port International Passenger Terminal (http://www.busanferry.co....) is the largest seaport in the country and offers ferry rides mostly to and from Japan. There are fairly frequent ferry connections from Busan to Japan. JR's Beetle hydrofoil service from Busan to Fukuoka manages the trip in just under three hours with up to five connections a day, but all other links are overnight slow ferries, such as Pukwan Ferry Company (http://www.pukwan.co.kr/)'s services to Shimonoseki from cost from $US60 one-way. A Busan-Osaka ferry is operated by Panstar Line Co., Ltd. (http://panstarline.com).
Incheon's International Ferry Terminal 1 Yeonan Budu, ì°ìë¶ë has services to several cities in China, such asWeihai, Dandong, Qingdao and Tianjin. The largest operator is Jinchon (http://www.jinchon.co.kr/), but Incheon Port has full listings on their website (http://www.incheonferry.co.kr/). The Chinese ports of Rizhao, Rongcheng and Lianyungang, all in Shandong province, can also be accessed by ferry from Pyeongtaek.
There are also weekly departures from Sokcho Gangwon-do to Vladivostok from US$270 operated by Dong Chun Ferry Co. Ltd. (http://www.dongchunferry.co.kr).
Travel from North Korea and hence anywhere else in Asia to South Korea by train remains impossible in practice. There have been a few test runs on the newly rebuilt railroad connecting the two, but it will likely remain more of a political statement than travel option for some time to come. However, for travelers coming from or continuing on to Japan, special through tickets (http://www.korail.go.kr/2...) are available, giving discounts of 30% on KTX services and 9-30% on Busan-Fukuoka ferries as well as Japanese trains.