+edit 2020-10-25:
Looks like there's some concrete documentation as of API v49.0 (Summer '20). The documented limit is 16,384 bytes.
The recommendation is to limit the URI to 2000 bytes, and headers to 8000 bytes.
+edit 2019-6-26:
Re-ran my code here, and came up with a limit of 16057. Looks like this number might vary from release to release, between pods, or perhaps some other criteria I am unaware of.
Original answer
Through trial and error, I was able to determine that Salesforce's limit on the URI length is 16,384 bytes (16,088 characters was my original finding).
Beyond that, Salesforce begins returning
System.HttpResponse[Status=Request Header Fields Too Large, StatusCode=431]
At 16,410 characters long, Salesforce returns
System.HttpResponse[Status=URI Too Long, StatusCode=414]
And finally, once the URI hits 32,435 characters, Salesforce croaks and we get the following exception
System.CalloutException: Unexpected end of file from server
This was determined with the following anonymous apex
// Setting up things for the JWT OAuth flow
// My connected app is set for admins selecting who is pre-authorized
String iss = '<client key of connected app>';
String aud = 'https://test.salesforce.com';
String sub = '<username for sandbox>';
Auth.JWT jwt = new Auth.JWT();
jwt.setAud(aud);
jwt.setIss(iss);
jwt.setSub(sub);
// 'Sandbox_Data_Populator' is the unique name of a self-signed certificate stored
// in Salesforce.
// This same cert is used as the digital signature for my connected app
Auth.JWS jws = new Auth.JWS(jwt, 'Sandbox_Data_Populator');
String tokenEndpoint = 'https://cs52.salesforce.com/services/oauth2/token';
Auth.JWTBearerTokenExchange bearer = new Auth.JWTBearerTokenExchange(tokenEndpoint, jws);
String accessToken = bearer.getAccessToken();
// Time to build the REST request OF DOOM!
// I have an Apex webservice whose URI is /services/apexrest/recordType
String endpt = '/recordType?s=';
// Start making the value to place in the query string
String qs = 'repeat';
// make it nice and long
endpt += qs.repeat(2725);
// and add some fine grain control
endpt += 'a'.repeat(1);
// Make the callout
// In this case, I'm calling out to the same org that I'm running this anonymous apex in
req.setEndpoint('https://cs52.salesforce.com/services/apexrest' + endpt);
req.setHeader('Authorization', 'Bearer ' + accessToken);
req.setMethod('GET');
res = httpObj.send(req);
The precise values at which Salesforce returns the different HTTP codes and exception were determined by tuning qs.repeat(2725); using a binary-ish search approach.
I started at qs.repeat(5000);, went down to qs.repeat(2500);, up to qs.repeat(2750);, etc... until I found the coarse limit, then I adjusted 'a'.repeat(1); (only need to go from 0 to 5) to find the exact limit.
Keep in mind that this limit appears to be for the entire URI. If you're using a longer URI, like say "https://my.custom.domain.salesforce.com", that'll eat up a few more characters than my "https://cs52.salesforce.com" does.
We can have up to 800 custom fields (or even more if you have managed packages installed) at a maximum of 60 characters each (40 for field label + __c + 15 for namespace + __), so it is possible to hit this limit if you attempt to query all fields on an object through the REST API...but that's not something most people will need to worry about.
