The common way to do it would be to send a POST to http://mydomain.com/hs/add
with the content:
name=John&score=987
(for simple urlencoded data, would be different for e.g. multipart encoded data; the format of the POST request body is arbitrary and outside of the scope of REST recommendations – it could even be arbitrary encrypted data, as others have suggested).
A GET request for adding a new highscore would not only be a violation of REST principles, but also a violation of RFC 2616, which requires GET requests to be idempotent.
EDIT
Is it bad practice to pass data in the query string and post an empty body?
Yes. The URL should describe the resource that's being subjected to the action described by the HTTP method. Hence, probably the best option would be to have http://mydomain.com/hs
as an URL and let the body completely describe the action.
The query string could possibly be used to further qualify requests without a body, e.g.:
http://mydomain.com/hs?period=lastmonth
(GET)