There are quite a few routes to travel by sea between China and South Korea. Most of them go through the Port of Incheon and that is what my answer will cover.
Routes
The following is a map from the Port of Incheon. It shows the passenger routes to China. I added the English names in white.
There are two International Passenger Terminals in Incheon. The orange lines indicate the 1st International Passenger Terminal and the yellow lines indicate the 2nd International Passenger Terminal.
It is easy to get from Incheon to Seoul by subway.
Schedules
Here is a table showing the schedules to the different cities. The image comes from the information desk at the Port of Incheon.
(If someone wants to edit my answer and put this in text form, please do.)
You can figure out the time that the ferry leaves or arrives in the Chinese ports by adding or subtracting the travel time from the arrival/departure time in Incheon.
It should be noted that ferry service may be suspended at times. I imagine for a bad storm, for example. Also, I think at least the Weidong ferry stops running during Chinese National Holiday and Chinese New Year.
Tickets
It appears that the tickets are all around 120,000 wan ($120) for economy. However, when I took the Weidong ferry it was discounted to about 75,000 wan. You might be able to get a discount if you by round trip tickets, too.
Every time I've taken the ferry I always just get to the ferry terminal at least 3 or four hours early and just buy my ticket when I get there. They never seem to be sold out. However, it is possible to buy tickets early. I just learned that you can do it with Ctrip. I will probably try that next time. But if you can't figure out how to get it beforehand, just arrive early at whatever harbor you are leaving from and buy it there.
You have to pay for the tickets in the currency of the country the port is in (of course).
Conditions
The ferries are not cruise liners but they are a very nice way to travel.
I always buy economy tickets (which are supposedly mats on the floor) but I have gotten a free upgrade to a bed every time.
There are showers and public bathrooms, which are kept fairly clean in my experience.
There are dining halls. Sometimes the meals are included in the ticket price (Tianjin ferry) and sometimes they cost extra (Qingdao ferry).
You can walk on the deck or observe the passing water from behind windows.
Getting to and from the port
Incheon
There are two ferry terminals in Incheon. From the map they looked pretty close but it turned out to be an hour and a half walk between them. The bus was much faster on the way back.
2nd International Passenger Terminal
The Sinpo subway station is on the street very close to this ferry terminal. Here is a map.
You can get to or from the Sinpo station by going to the nearby Incheon Subway Station, which is at the end of Line 1.
1st International Passenger Terminal
Although I haven't traveled from this terminal, I went inside and looked around. It is bigger than the 2nd terminal and there are ticket counters for each of the cities listed above for this terminal.
To the right of this terminal there is another building that appears to be for domestic ferry travel.
I'm not aware of a subway stop near this terminal, but you can take bus 24 to or from the Sinpo Subway Station.
Tianjin
If you are going to Tianjin by train, then go to Tanggu (塘沽) rather than Tianjin. The actual stop for the high speed train is Yujiabao (于家堡). Even from there it is quite a long taxi ride to the harbor. Tell the taxi driver to go to 天津国际邮轮母港. This is not the easiest harbor to get to. The timing was also a little tight getting there in the morning before the ship left. But it worked out and it was a very nice trip.
Qingdao
The ferry terminal is not that far from the train station so it is quite convenient to get in and out here. As I recall, busses 8 and 303 both made the trip. A taxi ride shouldn't be too expensive, either.
Other port cities
Feel free to update this post (or add another answer) if you have experience taking the ferry out of other cities.
Further reading
The following websites are not all in English but with a little Google Translate magic, you should be able to navigate them.
Other English reference pages