Step 1: Create the Prospective Partner Organization
Create a new Organization and set the Type to "Prospective Partner" (the ID for this is 3). This will automatically create a corresponding RecruitingOpportunity, which keeps track of who internally is assigned to recruit the partner prospect (default = nobody) and what stage in the recruitment process the partner is in (default is based on your recruitment stages settings). If you want to change these defaults, you can query the API to look up the RecruitingOpportunity for the newly created Organization, and then save it again with your changes.
Step 2: Create a Contact
Now that you've created the Organization, the next step is to create a contact at that Organization that represents the primary contact person at the prospective partner. This is done through the API by creating a User record and setting the type to "Contact" (the ID for this is 4). Don't forget to set the User's OrganizationID to the prospective partner's Organization key and IsKeyContact to "true". While collecting personal contact information and creating a contact is not required, it creates a more complete partner record and improves the recruitment process.
Step 3: Update the Prospective Partner Organization with the Primary Contact
The last step is to update the prospective partner record and set the PrimaryContactUserId to the User created in the previous step. Again, this is not required, but setting the primary contact improves the quality of your data.