If you're genuinely concerned with keeping your API RESTful, sending credentials on the querystring is definitely a no-no, since in REST the whole URI is an opaque identifier for a resource, and using cookies is an unnecessary coupling between the service and HTTP. The correct way to authenticate would be whatever is allowed and standardized by the protocol, so, in your case, through the WWW-Authenticate and Authorization headers. The clients should send their username and password in an Authorization: Basic header on every request (always use SSL, of course).
If you really want to use a token after the client is authenticated with username:password, you can also accept it as a custom authorization scheme, in the same header. For instance, something like:
Authorization: MyCompany apitoken="12k9023nd02890382n8902"
Whenever you're in doubt about what's the RESTful way to do something, just think what's the standard for the protocol you're using. That's one of the constraints behind REST. Whenever you have to document something that is replacing an standardized functionality, you're doing it wrong. If the standard isn't enough for your needs, it's fine to add something, like the custom auth scheme with the token here.