The short answer is "marathon cycling". Others have called it "touring with time limits".
As a sport, randonneuring is based on rules laid out by Audax Club Parisien (ACP). Rides are known as "brevets" and are organized by local clubs. They may have slightly different interpretations, but you can count on brevets being basically the same around the world.
I won't go into all of the gory details, but here are some of the highlights:
Randonneuring is a non-competitive sport. You get credit for finishing a ride within the time limits, but there are no rankings, no awards for coming in first or setting a great time. Some ride just to see if they can finish, others are trying to set new personal best times. This means that you can team up with a group of similarly paced riders and help each other make it to the finish, which is very helpful when you're new to the sport. All the riders I've ever met have been very generous with information, tips and motivation during brevets.
Riders must be self-sufficient. You're riding on regular roads without a sag wagon or cheering throngs of spectators. Some brevets might have a lot of volunteers, so there may be food & water at some of the checkpoints. Other rides might only have someone at the start & finish. In between, you're on your own so you need to be able to sort out mechanical problems and take care of food & hydration. Being prepared is essential since some routes can send you through very remote areas.
Controls (or checkpoints): you have to follow the specified route (instructions given out at the start, or possibly in advance) which passes through a series of controls. At each control, you need to get proof of passage. Typically this means getting a control card signed or stamped. Sometimes this might be done by volunteers, other times it's a bewildered 7-11 clerk or cafe owner.
Time limits: there is a time limit to make it through each control, including the final (finish) control. The limits are generous and are based on maintaining 15km/h for rides 600km and under. Keep in mind that this includes rest/food breaks, mechanical problems etc so you need to average above 20km/h to keep ahead of the cutoff times.
Distances start at 200km. A basic series would be a 200km, 300km, 400km and 600km brevet (depending on your club they might be spaced 2 weeks apart). So for a 200km you have 13.5 hours to finish; 600km has a 40hour time limit. It's a running clock, so the longer distances will involve plenty of night riding (on a 600km it's possible to build up enough of a time buffer for 4hrs of sleep, more if you're really fast). Other distances include 1000km and most of the premier events are 1200km (90hr limit, typically), including Paris-Brest-Paris.
Paris-Brest-Paris (PBP) is the biggest event on the randonneuring calender. This is a 1200km event which draws thousands of riders from around the world. It only runs every 4 years, and 2011 is the next one. Participation in randonneuring clubs usually spikes during a PBP year, so it's a great time to get into the sport as there will be many other new riders.
My favourite resource is the BC Randonneurs website (very biased, since I'm a member). The links at the bottom of the page go into more detail on what I've covered. Randonneurs USA will probably be useful if you're looking for a US-based club.
If you love riding, enjoy challenges and are very persistent (read "stubborn") than I'd highly recommend it. Most clubs run shorter rides called "populaires" which are open to non-members and give people a chance to try the sport with only a 50-100km committment.