How do airliners cross the ocean without GPS?
Do they use dead-reckoning or are there navigation aids floating out there?
Well, most airlines do cross the ocean with GPS in today's world.
That being said, most (if not all) transcontinental airliners, and many flying domestic routes as well, have what's called an inertial navigation system (a form of dead-reckoning where gyros and accelerometers are used to compute changes in position). The INS feeds into the flight management computer which is used to cross-check the GPS position, and can be used as a primary navigation source should the GPS signal be lost or corrupted.
Prior to GPS, inertial navigation was the primary means of navigating across oceans. However, a great many airplanes did cross oceans before INS... with varying success. The general idea was to use a combination of dead-reckoning, radio beacons where you can find them (small islands and coastlines), the sun (with the help of a sextant) during the day, and the stars at night. Hopefully, this puts you in position after some period of time to pickup ground-based navigational aids, or to identify a coastline. This actually works pretty well if your wind estimates are good, and the margin for error is high enough. As DeltaLima points out, long-range radio navigation systems also started to emerge around World War II (LORAN and Decca) which had a much greater range than previous radio beacons, and therefore decreased the amount of time required to fly by dead-reckoning alone. By the time inertial navigation became prevalent in the 1970's, airlines were already providing reliable transcontinental passenger flights every day.
Another possible outcome is that your plane is lost in the ocean, never found, and the Discovery Channel funds an expedition to look for you 75 years later.
In the days before GPS, we routinely crossed the oceans using inertial navigation systems.
The system I was familiar with used 3 separate inertial systems (Carousel was the brand name). You could choose to navigate by any single one, but the most common way of using them was to have the autopilot "average" the positions. You could also choose to exclude any given INS, in which case if you were averaging, you were averaging only two.
For the North Atlantic MNPS airspace system, You manually updated each INS passing over your last known ground position fix. When you passed over your first ground-based nav fix on the other side, you again manually updated the INSes with that information and then recorded in the maintenance log how far off left or right each INS was in the maintenance log. There were standards. Offhand I'm not sure I am remembering them correctly, but what I seem to recall was a max error of 2 nautical miles per hour flown without update. The MNPS had at the time a max error allowed without penalty of 10 nautical miles left or right of course. If that was exceeded, points were deducted from your company's score. Lose enough points and the company would not be allowed in fly in MNPS.
Off course errors of two to six nautical miles for a crossing were typical.
There is the story, true or not I do not know, of the captain who, when hand held GPSs first became available, used one to cross the North Atlantic, and had a near zero off course error. When ATC complimented him on that, he blurted out that he had used his hand-held. He was subsequently violated for using a non-approved navigational system. Whether the incident really happened, I don't know, but an airline's FAA approved op specs specifies not only which navigation methods are to be used but also which systems by brand and model name (at least back when I was flying).
Most aircraft cross the atlantic by GPS, usually with INS as backup. INS as the primary form of navigation is still used as well.
Omega was shut down in 1997, Decca in 2000 and LORAN C ceased in 2010.
They do use GPS, with backups, as the other answers describe.
If your question is inspired by MH370, remember that GPS tells you where you are: it doesn't tell anyone else where you are. GPS works by having a bunch of satellites sending out signals and, based on the signals you hear, you can calculate your own position. A GPS user doesn't transmit anything back to the satellites. What MH370 lacked was a system that was reporting its location back to base.
Mode of air navigation I've witnessed: