Many of my books have deckled edges; I'm sure there have been various occasions when I've chosen the deckled-edged version when faced with a decision between editions. I agree with Erin that materials are always an important choice for a designer. I think Allison told us in Type that we should always choose our paper before even beginning a design as the paper would alter colors, determine what size type would be legible due to its amount of bleed, etc. But, as we discussed in the printers posts, I've always printed in the lab so I've let myself default to the paper that's automatically there. I've bought some paper online for the final version of the book--hopefully it arrives and is what I want it to be in terms of how it looks/feels.
To answer your question(s), Andrew, I do think that certain materials make more sense for some books than others. While I like a deckled edge, and imagine that it would be a nice touch for just about any novel, I go back to the design for 1Q84, which I love so much. Those decisions made sense for this strange novel about an alternate universe where really strange things happen and the fantasy novella written by a seventeen year-old turns out to be true, but it might seem completely excessive to use a vellum cover like that on another novel. I love little touches like spot varnishes and sometimes even embossing, but they have to make sense conceptually with the design and the book.
As to Shannon's question, I haven't been in person to any paper stores in the area; I've heard good things about the Paper Source (again, I think that was from Allison...?), but so much of what is available is online only, and you have to guess and hope with that. Jeanne talked about getting free paper/ink sample booklets, and though I've looked online at the booklets from Mohawk, I haven't requested any yet.
For the publishing industry, though, I'm not sure entirely how much choice the book designer has in the matter of materials, to address another of Shannon's questions. It seems like in book design, more than in other areas of design, there are so many people involved in the decision-making process that it could be difficult to get the publisher to take a chance on something more expensive. Yes, I think it's definitely more likely that they would splurge on materials for a book written by someone well-known (again, look at 1Q84: Murakami is one of the most well-known authors writing today, that novel had become somewhat of an event because he'd worked on it for so long, he has a following/what publishers call a "platform"--he even has his own drinking game and stickers based on tropes he tends to use--and everyone knows that what he writes is going to be weird, so the readership would probably expect a novel design that is a bit singular as well as a bit luxurious). But a novel's design moves from the designer to the art director, to the marketing team, to the editors, to the author, and at any of those places, there are recommendations and decisions being made about the design.
And I think size decisions are made even before the design is started, so that would be where the paper quality decision is made (as it would determine spine size). Also, there are usually certain consistencies among books from the same imprint--Knopf or Penguin would probably be more likely to use deckled edges than their subsidiary crime fiction imprints, for example--and imprints have series that also probably limit the designer's choices as to more expensive materials. I think it's a decision made between the editor(s) of a specific novel and the art director of the imprint how many pages a book will have, how large a format they'll use, the print run, and the materials. So, while a designer may be able to argue for extras with certain books, it's not always the designer's decision. That being said, I'm not sure how much more say designers might have at independent publishers.