Take the Ferry from Fukuoka to Pusan, cost around 8500yen for the overnight ferry and the 3 hours ferry cost 13000 yen.
There is a page where someone collected the informations on all the ferrys.
Randy's 'Favorite Getaways in Rural Japan' -- INTERNATIONAL FERRIES
The easiest would be to take the fast ferry, because there site is in English
Beetle English
but it is off course more touristy and a little bit more expensive. I think from Pusan you should be able to catch a overland bus to Seoul for some bucks.
Firebird