Error reporting in a C library

Question

I am looking for a robust way to report errors in a C library. Consider the simple example of a queue:

struct queue *q = malloc(sizeof(*q));
if (NULL == q) {
    /* malloc failed. now what ? */
    return NULL; /* maybe ? */
}

Okay, so for that example returning NULL isn't otherwise valid so it makes sense to return it to signal an error. But

void *get_data()
{
    /* stuff */

    /* Error detected. NULL is a valid return, now what ? */

    /* stuff */
}

What's more, once we signal an error, how to signal what is the error ? I have thought about it and don't have a satisfying solution.

Using errno or some other global object isn't something I would like to do (perhaps the functions may be called from multiple threads etc).
I thought of making the client supply some "status" object that can be inspected after the call, but that would make the API quite ugly.

So what's your take on the subject ? How do you report errors in a clean way ?