aria-label, aria-labelledby and aria-describedby:

I just noticed that although the aria-label, aria-labelledby and aria-describedby attributes are said to work on every element (see http://www.w3.org/TR/wai-aria/states_and_properties#aria-describedby), they only seem to work for a few elements like a, and not for e.g. div or p in NVDA and JAWS.

I have created a small codepen to demonstrate the issue (browse it using browse and focus mode):

http://codepen.io/jmuheim/pen/avWbPe

For example, in NVDA, on the a element, the aria-label and aria-labelledby seem to work in both browse and focus mode. But aria-describedby is only announced in focus mode, not in browse mode.

For the input element, none of the attributes seem to work in browse mode, but all work in focus mode.

For "bare" text elements like p or div, none of the attributes seem to work.

In JAWS, it's quite similar behaviour, but at least for the p element, when there is an aria-describedby, it announces that a description can be read by pressing "JAWS + alt + r".

I don't really see a clear pattern for this, so I wonder what are the general rules in screenreaders on how to use these attributes? Or better: why don't they simply work for every element, as the spec proposes?

ARIA does not define how assistive tech are to expose UI. It does define how browsers are required to expose roles, states and properties via accessibility APIs. It's the same with HTML in general, the HTML spec does not define/require UI, that is left up to the browsers to decide. In the case of aria-label (for example) it is a requirement in ARIA that aria-label is mapped to the accessible name property in accessibility APIs, it is not a requirment that screen readers announce it, or not, on any given element (i.e. expose as part of the aural UI). General observed rule is that screen readers will announce accessible names and accessible descriptions on interactive elements. They will announce accessible names on most grouping elements and sectioning elements. They will announce neither on most text level elements.

Note: the above also applies to any element that has it's default semantics overidden with ARIA roles. For example ARIA widget roles will have both acc name and description announced, like native HTML interactive elements.