これが私の解決策です。
String url = "https://graph.facebook.com/me/photos";
File file = new File("path");
ClientConfig cc = new DefaultClientConfig();
cc.getClasses().add(MultiPartWriter.class);
Client client = Client.create(cc);
WebResource webResource = client.resource(url);
FormDataMultiPart fdmp = new FormDataMultiPart();
fdmp.bodyPart(new FileDataBodyPart("source", file, MediaType.APPLICATION_OCTET_STREAM_TYPE));
fdmp.bodyPart(new FormDataBodyPart("message", "YAY I did it!"));
fdmp.bodyPart(new FormDataBodyPart("access_token", accessToken));
ClientResponse response = webResource.type(MediaType.MULTIPART_FORM_DATA_TYPE).post(ClientResponse.class, fdmp);
String string = response.getEntity(String.class);