What is RDS?
RDS, or Radio Data System, is a system developed to transmit data along with a broadcast.  There are several applications of RDS, including (most importantly for DX'ers) instant identification of a station.

RDS data can include station identifications, format information, "radio text", alternate frequencies, and current time.  Radio Text can be programmed to whatever a station wants.  Frequently, it is programmed as the station's slogan and/or telephone number.  Less frequently, it can be programmed to display advertisements or the artist/title of the current song.

RDS is more widely used in Europe than in North America.  Many European networks take advantage of the "alternate frequencies" function, which allows a user to keep listening to a given network's program even while traveling in and out of different stations coverage areas.

RDS has other applications as well, such as radio paging and traffic updates.

RDS and DX'ing
In order to take advantage of RDS, you need to have an RDS capable receiver or tuner.  There are many such radios available, ranging from high-end tuners like the Onkyo T-4711, to home theatre stereo receivers like the Kenwood 1090VR, to small portables like the Sangean ATS-909 (aka Radio Shack DX-398), and car radios like the Kenwood KRC-605.  In fact, it appears that most new aftermarket car radios have RDS capability, and some factory default radios do, too.

However, if you really like your existing tuner or receiver, there are after-market devices that can be connected to your tuner/receiver.  The most popular unit among DX'ers is the Conrad RDS Manager.  It is a stand-alone unit, about 4.5 inches long, 2 inches high, and 3 inches deep, with an LED display.  The Conrad is connected to a tuner's MPX horizontal output by way of an RCA jack.  (The MPX output is used since the higher frequencies where RDS siganls are are not filtered).  If you do not have an MPX output on your tuner (usually only medium/high end components have them), you will have to experiment and find a tap point on the circuit board.

The Conrad RDS Manager can also be connected to your computer via a serial port.  This solution is actually the preferred solution for DX'ers, as it allows you to retain the RDS display information, whereas the unit will flush the info if it loses the signal.  Additionally, the computer software displays PI code information.  PI codes can be translated into call signs in the USA, and usually show up at a weaker signal threshold than the station ID's.

Once you are set up with an RDS capable receiver/tuner, you will quickly start to see the benefits.  Even though only a small percentage of USA stations use RDS, you will be able to quickly identify them if their signal is strong enough.  This is very beneficial at the start of a sporadic-E opening, where you might not know exactly where the stations are coming from.  RDS is also very useful for meteor scatter DX'ing, as one can leave a tuner and PC on overnight and log "unattended" DX.

LINKS
RDS List (USA and Canada)
RDS Forum's Website
RDS Info for the United States - links and info useful to experimenters and DX'ers
A large list of RDS capable receivers
RDS Logbook - listing of RDS stations based on DX'er reports [note stations add and drop RDS frequently]