To me, notable means something which is known outside of a narrow interest group or constituency, or should be because of its particular importance or impact. It's an extension of the notion of "notoriety" for biographical articles.
I've heard it argued that "notability" is not a criterion for deletion, because (among other things) this isn't specifically stated in the Deletion policy; and since Wikipedia is not paper with (in theory) no size limits, there's no reason we shouldn't include "everything" that fits in with our other criteria, such as verifiability and no original research. In other words, a subject's perceived "importance" or "fame" is no criterion for deletion or inclusion.
I propose that notability, while directly pertaining to importance and fame, is also a useful surrogate for the notions of verifiability and original research, since those, in turn, go hand-in-hand with notability--at least, by my definition.
Since Wikipedia is not a primary or secondary source, much less a vehicle for publication of direct observation, non-notable subjects do not belong in it. Inclusionists have said, "Why not write an article on your next door neighbor's dog, as long as it's verifiable and NPOV?" Well, for one, because it's original research--your direct observations of the dog. If the dog appears in a reputable publication, that's another story.
Notability also speaks to verifiability. There is a level of ease with which facts can be checked that must be maintained in order to be verifiable in a practical sense: theoretical verifiability isn't enough. Your garage band in Seattle may consist of Mike, Jeff, Scott and Mike, and that may theoretically be verifiable (if I traveled to Seattle); but that's not enough. I need to be able to look it up in a book, or on the web or something. And not just any source: blogs, zines, e-zines, stuff you printed up, CDs you recorded yourself, etc. don't count as "sources."
And a single source isn't really enough. No context or comparison is possible with a single source. The standard could apply to things which are public record (after all, many of us have birth certificates but that doesn't make us notable) or are mentioned once or twice in public works. Notable subjects will provide a choice of sources--even if only one is cited to begin with, future editors have the opportunity to counter, compare and revise according to information in other sources. Without this choice of sources, this isn't possible. (It's also a principal reason why Wikipedia is not a reference to fictional worlds).
Edge cases and precedents
I'm not convinced by the argument that if a line (such as a line for notability for some particular class of subjects) is ambiguous or hard to draw, then it's not worth having a line. Drawing these lines is precisely why we have mechanisms like VFD; I think the wrangling Wikipedia-style process for drawing ambiguous limits gives good results. My own policy is that edge cases (as I perceive them--that is, subjects which are edge cases to me) stay. When in doubt, don't delete.
I find it even less convincing to argue "if we can have an article on... then we can have this." First, just because you make a mistake once does not mean you are doomed to make the same mistake again and again for the sake of consistency. Second, I don't really see any value in consistency for its own sake.
"Deletion" is an unfortunate term. Deletion and transwiki-ing are the same thing, and they mean "this information doesn't belong here, because this is an encyclopedia." That doesn't mean it doesn't belong somewhere else. We say transwiki because Wikimedia hosts other projects, and so we can say (at the same time that something is deleted) that it belongs somewhere else, because we know something about those other places.
Deletion is a charged word that makes it sound like I want to destroy information. I prefer "exclusion." If I vote delete it doesn't necessarily mean I think the information shouldn't exist; just that it doesn't belong here and I don't (within the context of this project and its sisters) know where it should go.