North on Nykøbing Falster, , Copenhagen towards
There are no good places to stand to hitch, but just out of the Scandlines ferry terminal there is a place you can stand just before a street to the right and cars have the possibility to stop. Basically walk away from the ferry next to where the cars are driving and you will see it. Trucks must stop and pay the toll for the road so it is possible to ask drivers. DK trucks are not allowed to take passengers so focus on other trucks.
If you get stuck there is bus 39 that drives to Nykøbing Falster which costs EUR 5 and is the only transport in Gedser. There is no bus between 23:00 and 04:00. It can be easier hitching from Nykøbing F because there are more cars.
South towards Germany
The Scandlines ferry to Rostock charges by vehicle regardless of the number of passengers, so it is possible to hitch a ride with a car. If you buy a ticket it will cost DKK 50. The timetable can be found here. Ask people on the ferry if they are going in your direction, it shouldn't be hard to find a ride to Berlin or Hamburg.
Marcel thinks this ferry is pay per passenger, not pay per car: In 2014 he hitched a car that took this ferry from Gedser to Rostock. His luck there was no person at the terminal getting on the ship, only a computer scanning the driver's ticket and asking how many people there are in the car. His company ticket had "1 person" written on it, Marcel asked the driver to hit the button for 1 person. He did and the bar lifted up. I don't know what would have happened had he pushed the button for two people in car.
August 2018: Thelonebaker was able to successfully hitch the ferry coming from Denmark. He had a ride from Karlslunde who happened to be heading this direction with a prebooked ticket for 2 people. At the gate the driver simply said 3 passengers when asked and a moment later they were passing through the gate. Though the ticket itself still said 2 passengers. The ferry is definitely still paid by car as the passengers charge read zero euro. And if you read the information on the site it is apparently actually up to 9 people in a vehicle allowed as opposed to 4.
October 2020: NellyR managed to find someone who let him stay in the car to get on the ferry - it was still no additional costs for them. But it seems that the pedestrian tickets are a lot more expensive now. He talked to someone who paid 40 Euro for their ticket.