Jeju is actually a very mainstream destination for Koreans, if not so well known to westerners. It is very developed for tourism and until recently when Korea started to become a wealthy country it was the de facto destination for honeymooners. You might think of it as Korea's equivalent of Australia's Gold Coast or USA's Hawaii. For Korea it's far south, but it's not tropical.
As per being a top local tourist destination there are many ways to get there.
WikiTravel actually has a pretty decent section on getting to Jeju by boat.
And there is also an official page on ferries to and from Jeju on the Visitkorea site.
Busan (Korea's second-biggest city, at the south of the mainland)
Two vessels. Trips every day except Sunday. 10 - 12 hours.
Incheon (Where Seoul's International airport is, in the northwest of the mainland)
One vessel. Monday, Wednesday, and Friday only. 13½ - 15 hours.
Mokpo (At the southwest corner of the mainland)
Three vesslels. Every day of the week. 3 - 5½ hours (depending on vessel).
Wando (At the southern tip of the Korean peninsula)
Three vessels. Every day of the week. 3 -3½ hours.
Yeosu (About halfway between Wando and Busan on the south of the Korean peninsula)
One vessel. Every day of the week. 7 hours.
(The trip durations are compiled from several sources which do not completely agree so I've included a range from the quickest I found to the slowest.)
Asia-planet.net has a nice page with a map showing where these and all other ferry ports are in Korea.