Como faço para construir um URL ou URI em Java? Existe uma forma idiomática ou bibliotecas que fazem isso facilmente?

Preciso permitir iniciar a partir de uma string de solicitação, analisar / alterar várias partes de URL (esquema, host, caminho, string de consulta) e oferecer suporte à adição e codificação automática de parâmetros de consulta.

A partir do Apache HTTP Component HttpClient 4.1.3, do tutorial oficial :

public class HttpClientTest {
public static void main(String[] args) throws URISyntaxException {
    List<NameValuePair> qparams = new ArrayList<NameValuePair>();
    qparams.add(new BasicNameValuePair("q", "httpclient"));
    qparams.add(new BasicNameValuePair("btnG", "Google Search"));
    qparams.add(new BasicNameValuePair("aq", "f"));
    qparams.add(new BasicNameValuePair("oq", null));
    URI uri = URIUtils.createURI("http", "www.google.com", -1, "/search",
                                 URLEncodedUtils.format(qparams, "UTF-8"), null);
    HttpGet httpget = new HttpGet(uri);
    System.out.println(httpget.getURI());
    //http://www.google.com/search?q=httpclient&btnG=Google+Search&aq=f&oq=
}
}

Editar: a partir da v4.2 URIUtils.createURI()tornou-se obsoleto em favor de URIBuilder:

URI uri = new URIBuilder()
        .setScheme("http")
        .setHost("www.google.com")
        .setPath("/search")
        .setParameter("q", "httpclient")
        .setParameter("btnG", "Google Search")
        .setParameter("aq", "f")
        .setParameter("oq", "")
        .build();
HttpGet httpget = new HttpGet(uri);
System.out.println(httpget.getURI());

Como autor, provavelmente não sou a melhor pessoa para julgar se meu construtor de URL / URI é bom , mas aqui está: https://github.com/mikaelhg/urlbuilder

Eu queria a solução completa mais simples possível com zero dependências fora do JDK, então tive que lançar a minha própria.

Apache HTTPClient ?

Usar HTTPClient funcionou bem.

protected static String createUrl(List<NameValuePair> pairs) throws URIException{

  HttpMethod method = new GetMethod("http://example.org");
  method.setQueryString(pairs.toArray(new NameValuePair[]{}));

  return method.getURI().getEscapedURI();

}

Existem muitas bibliotecas que podem ajudá-lo com a construção de URI (não reinvente a roda). Aqui estão três para você começar:

Java EE 7

import javax.ws.rs.core.UriBuilder;
...
return UriBuilder.fromUri(url).queryParam(key, value).build();

org.apache.httpcomponents: httpclient: 4.5.2

import org.apache.http.client.utils.URIBuilder;
...
return new URIBuilder(url).addParameter(key, value).build();

org.springframework: spring-web: 4.2.5.RELEASE

import org.springframework.web.util.UriComponentsBuilder;
...
return UriComponentsBuilder.fromUriString(url).queryParam(key, value).build().toUri();

Veja também: GIST> Testes de Construtor de URI

Use OkHttp

É 2020 e há uma biblioteca muito popular chamado OkHttp que foi estrelou 35K vezes no GitHub. Com esta biblioteca, você pode construir um url como abaixo:

import okhttp3.HttpUrl;

URL url = new HttpUrl.Builder()
    .scheme("http")
    .host("example.com")
    .port(4567)
    .addPathSegment("foldername/1234")
    .addQueryParameter("abc", "xyz")
    .build().url();

Depois de ser criticado por sugerir a classe de URL. Vou seguir o conselho do comentarista e sugerir a classe URI . Eu sugiro que você olhe atentamente para os construtores de um URI, pois a classe é muito imutável depois de criada.
Acho que esse construtor permite que você defina tudo no URI que você possa precisar.

URI(String scheme, String userInfo, String host, int port, String path, String query, String fragment)
          Constructs a hierarchical URI from the given components.