Definition
Embossing is a raised relief that is made in paper. You can run your fingers over it, and feel the tactile, raised items. Debossing is the opposite of embossing, it is a depression in the paper. And because papers have two sides, embossing or debossing is really a matter of perspective. We might emboss a LP cover by pressing from underneath, but flip it over and the back side is debossed. 

Embossing on spine blasucci title   Letter embossing on book packaging

Summary Embossing and Debossing are really the same thing, depending on perspective. Generally we refer to embossing as raised, and debossing as depressed.

What can be embossed?
Lettering is frequently embossed. Paper stock items, such as art card and cardboard covers are great candidates. Good examples include disc jackets, digipaks, vinyl record albums, book covers. Very thick cardboard is difficult to emboss. Leather is a great candidate for debossing. 

.

Does Foil Stamping result in embossed areas?
Foil stamping is generally flat. However, you can do an embossed area and try to align the foil and raised area. Registration can be tricky though, and you want to make sure the lettering or artwork is suitable. 
Special effects printing foil spot gloss embossing  Foil stamping aligned with embossing on cd book

How do you set up embossing the artwork? How do you proof embossing? 
Embossing (or debossing) goes on a separate layer in the artwork. Use something like cyan to designate it. Film is required to create an embossing or debossing plate, and you will need a press proof to check it. 

How much does embossing cost?
Embossing isn’t too terrible in cost. Expect to pay a several hundred at the smaller quantities. Larger quantities it adds anywhere from $0.20 per unit down to $0.05 per unit additional.