What does the difference look like? What is the advantage of using Spot Color over CMYK?
The difference is CMYK is printed with 4 colors (use a loupe to see the dot patterns, called a line screen, of all 4 colors). Spot colors are individual colors. They may be screened back but are often printed as a solid block of color.
Spot colors come in way more colors than what you can achieve with CMYK.
Note that both are often used together...4 color printing with one or two spot colors (This was a trademark of Wired Magazine back in the day...4 color printing and then they'd add one or two more spot colors in a metallic or day-glo color)
As Lauren says, there are colors that you can achieve with Pantone (or any of several other, similar brands) spot colors that are impossible in CMYK. Bright oranges and rich blues are beyond the capability of regular CMYK, for example. Color accuracy (or, perhaps, color certainty) is another major reason to employ spot inks.
If you look on the Pantone website you'll find some videos that explain (and extol the virtues of!) the system. Note that the solid colors are specified as "formula guides." That's because the colors are specified as exact mixing "recipes" of the standard Pantone base inks (14 of them), so that what the printer gives you will match what's in the Pantone swatch book.
In many cases, particularly stationery, the printing is done using only two or three exact colors: generally black plus one or two spot colors. A two-color job is often less expensive, and always more accurate, than a CMYK rendition of the same thing. This is the norm for stationery printing, and small shops catering to that market quite often won't even have a 4-color press.
If you are working in InDesign or Illustrator, you can select colors from the Pantone Solid Coated or Uncoated ranges for your artwork. It is very important, though, to keep "Overprint Preview" turned on while working with them, so you get an accurate rendition on screen of what will hit the paper when it's printed. This is particularly important if there's any transparency in your layout.
If you plan to work with Pantone solids, you should definitely buy swatch books for the colors you're likely to use. There are separate books for metallics and "pastels and neons". Don't rely on your monitor, no matter how well it's calibrated.
Spot colors are premixed ink. It will often print more precisely than CMYK, since the CMYK color space has some limitations in the range of colors it can produce.
Sometimes CMYK colors are muddier or darker than spot, but it depends on the color. Certain colors like metallics and some pastels can't be reproduced in CMYK and must be printed spot.
If it's a color which is possible to reproduce in CMYK, the main benefit of spot is color accuracy. This could be for a corporate color, like Coca-Cola Red or IBM Blue. Printing a color in spot, or printing it in a "double hit" (printing it once in CMYK and a second time, the same color, as a spot) can make it pop against a complex layout or on a magazine cover.
Whether you use spot or CMYK depends on your document, your color requirements, and your budget (as it could be a "fifth color" or "fifth plate" on top of the CMYK you're already printing).