Import Entries with Categories
Anyone curious about this answer, can checkout the GitHub thread referred to above:
https://github.com/boboldehampsink/import/issues/14

The most relevant comment for this answer is by boboldehampsink:

the documentation on category importing isn't complete yet. You have to fill in the complete path with titles, so: Category Title/Subcategory Title/Subsubcategory Title (for example)