Quoting from RFC 2616 (HTTP 1.1):
... if "*" is given and any current entity exists for that resource, then the server MUST NOT perform the requested method, unless required to do so because the resource's modification date fails to match that supplied in an If-Modified-Since header field in the request.
The RFC goes on to say that instead of performing the request, servers should respond with 304 (not modified) for GET and HEAD requests, and that they should respond with 412 (precondition failed) for all other request types. But that's only if the server actually has some version of the requested resource. If you don't have any entities, then you should handle the request (probably with a 404 since you don't have anything).
To handle a request, first figure out what the server would do if that header weren't present. If the result of that request would not be 2xx or 304, then serve the request as normal. But if the result of the request would be 2xx or 304, then handle the If-None-Modified case. When it's a star, then just return 304 immediately (unless trumped by If-Modified-Since). If it's one or more entity tags, then check whether any of those tags matches the tag of the thing you were planning on serving as a response. If there's any match, return 304; if there's no match, then serve it as you normally would.
Later in the RFC, there's more:
The meaning of "If-None-Match: *" is that the method MUST NOT be performed if the representation selected by the origin server (or by a cache, possibly using the Vary mechanism, see section 14.44) exists, and SHOULD be performed if the representation does not exist. This feature is intended to be useful in preventing races between PUT operations.
That is, the star allows the client to say, "Don't PUT this file if there's any version of this file already there."