Как перейти по URL Java?
Можно воспользоваться методом encode класса URLEncoder. Только нужно не всю строку с адресом перегонять через encode, а только GET-переменные. Можно так сделать:try {
    Desktop d=Desktop.getDesktop();

    d.browse(new URI(
        String.format( 
            "http://www.google.ru/search?sourceid=chrome&ie=UTF-8&q=%s", 
            URLEncoder.encode( "запрос с кучей пробелов" , "UTF8" )
        )
    ));
} catch (IOException ioe) {
    ioe.printStackTrace();
} catch (URISyntaxException use) {
    use.printStackTrace();
}
Все пробелы нужно заменить на '+'