I've been working on this for quite a while and while I don't have any answers I may have a little insight.
The ps3_productcategories table is as you correctly surmised made up of 3 auto-generated fields, it's own, one form ps3_products and one from ps3_categories. There really is no commonality between the tables that allows for easy linking so you have to create you own.
Since productID is a sequential number it gives no basis for linking. What I did was to create a table with a column for ProductID and one for ProductSKU then manually link CategoryID to ProductSKU. When finished I could delete the column for ProductSKU and I had the required csv for import. Not so bad if you have a small list but then you are better off to upload products one at a time.
(WARNING - Don't try this at home, it will lead to premature aging, an enhancement of negative vocabulary and possibly divorce.)
The csv files that Jason supplied are not csv but rather semicolon separated values. What this means is that rather than a separate column for each heading they are all actually in one great big column, each item separated by a semi colon.
I tried several times to get it to import and was finally successful by clicking on the first CSV and checking, Ignore Duplicate Rows. It did work, the import was successful and the products and categories connected properly. Unfortunately for us that is not a practical solution. It is okay to export a sheet using semicolon separated values but not at all practical to create one that way. It would be a humongous task to try to create a spread sheet for thousands of items with only one column and separating each item category with a semicolon. At least I wouldn't want to try it. One misalignment and the whole sheet is shot and good luck finding the error. Much easier to create the csv using separate columns for each field. But this is where my problem comes in. I have been able to import products and categories but so far importing productcategories this way does not provide the proper linking.
But that gives me an idea. I could save each column as text, use a program I have to put quotes around everything, then again to add a semicolon after each item. Then I could combine the two columns into one and try an import using semicolon separated values. That just might work.
There has to be an easier way but I'm obviously not bright enough to find it. Hopefully someone else out there has successfully created csv's and imported them into all three tables and would like to share.