Existem várias alternativas. Você pode criar um token de autenticação, assim como faz o webservice do mercado livre. Este token seria um codigo que é passado junto com a URL, ele dura por tantos minutos, é adquirido após o usuário fazer uma espécie de login.
Você também pode deixar seu webservice stateful, ou seja, manter estado de sessão dentro dele, assim verificando se o usário está logado (coisa que nãp é muito legal na minha opinião)
Ao infinito e além!