Onde exatamente na solicitação HTTP devem ser indicados os dados de autenticação, como login e senha?

Os dados de autenticação, como login e senha, geralmente são enviados no cabeçalho Authorization da requisição HTTP. A forma mais comum é usar o esquema Basic Authentication, onde o login e a senha são codificados em Base64 e enviados no cabeçalho:

Authorization: Basic base64(login:password)

Por exemplo, se o login for user e a senha pass, a string para codificação será user:pass.

Exemplo em Android usando HttpURLConnection:

String credentials = "user:pass";
String auth = "Basic " + Base64.encodeToString(credentials.getBytes(), Base64.NO_WRAP);
connection.setRequestProperty("Authorization", auth);

Enviar login e senha no corpo da requisição ou na URL (por exemplo, nos parâmetros GET) não é recomendado por motivos de segurança.