private HttpClient client = new HttpClient();

public void patch(...) throws Exception {
    PostMethod patch = createPost(instanceUrl + "/services/data/"
            + API_VERSION + "/sobjects/" + sobType + "/"
            + sobIdMap.get(oldSobId) + "?_HttpMethod=PATCH"
            );
    patch.setRequestEntity(new StringRequestEntity(update.toString(), "application/json",
            "UTF-8"));
    client.executeMethod(patch);
    if (patch.getStatusCode() == ...) {
        ...
    } else {
        ...
    }
}

private PostMethod createPost(String uri) {
    PostMethod post = new PostMethod(uri);
    post.setRequestHeader("Authorization", "OAuth " + sessionId);
    return post;
}