How to perform upsert in Salesforce Bulk API

From our comment thread on the OP:

1. You need to configure an external Id field on your object; this will generally by the primary key used by your external system with which you are syncing. See http://na1.salesforce.com/help/doc/en/faq_import_general_what_is_an_external.htm and http://na1.salesforce.com/help/doc/en/custom_field_attributes.htm
2. Change your operation to upsert and ensure the external Id is provided in your data file.
3. Edit Add the external Id to your XML (see Update 2 below)

Update 1

I don't think there are any changes to the HTTP POST request. Sample updated CSV as requested (some values shortened for improved formatting):

Id,FirstName,LastName,Department,Birthdate,Description, My_External_Id__c
"003i000000EpehQ","Tomas","Jones","MKG","1940-06-07Z","Awesome", "ExternalPrimaryKey1"
"003i000000EpYI7","Ian","Dury","R&D","","Expert", "ExternalPrimaryKey2"

Update 2

I found the XML definition needed to start the job here. Using cURL with the job.txt example provided by Salesforce, your XML should look like this:

<?xml version="1.0" encoding="UTF-8"?>
<jobInfo xmlns="http://www.force.com/2009/06/asyncapi/dataload">
<operation>upsert</operation>
<object>Contact</object>
<externalIdFieldName>My_External_Id__c</externalIdFieldName>
<contentType>CSV</contentType>
</jobInfo>

Note that capitalization and the order of the elements is important; if you put <externalIdFieldName> after <contentType> you will get a HTTP 400 error message stating it was unable to parse the job. After successfully submitting the job you will get an XML response with the job id, operation, object, etc... (see page 6 in the previously linked PDF.)

I recently had to use the Bulk API using C# so I started the Salesforce Bulk API Starter GitHub Project to allow others to do the same. The project contains a test project which demonstrates how to Query, Insert, Upsert, and Delete using the framework using CSVs.

The project can also be downloaded from Nuget using Install-Package SFBulkAPIStarter. The Nuget package doesn't contain the test project.