You can get from Korea to China by ferry. If you want to go from Seoul to Beijing, you can leave Korea from Incheon (20 km from Seoul) and arrive in Tianjin (100 km from Beijing). These are the closest sea ports to the capital cities.
The Jinchon Ferry travels between Incheon and Tianjin. You can phone them on this phone number: +82-32-777-8260. A man spoke English well enough for me to ask and answer questions. The phone number in China is: +86-22-2311-2842.
The ferries leave Incheon on Tuesdays and Fridays. The Tuesday ferry leaves at 13:00 (Korea time) and it takes 24 hours to make the trip. I wanted an economy ticket which costs 128200 KRW (about 100 USD). The man said I don't need to make a reservation since there were plenty of spaces available (but I don't know if it's like that all the time). The ferry leaves from Incheon International Ferry Terminal number 2. You can buy tickets from the terminal on the day of departure. Access to the terminal here: http://www.visitkorea.or.kr/enu/TR/TR_EN_5_1_5_2.jsp
Since you are going to China on this ferry, you will need to get a Chinese visa from a Chinese embassy. For Australians, many countries (like Japan, Korea, Singapore etc) will allow you to enter without a visa for tourist purposes (this is not legal adivce), but with China, you must get a visa, even to visit for a few days.
More Korea China Ferry info: