Categories can be imported using the Magmi utility. Magmi uses a plugin to generate categories on-the-fly, provided they are identified when importing products.
This tutorial explains how to use Magmi with a product import to create categories on-the-fly:
The
interface is slightly more complicated, however the flexibility and
options it offers are second to none. If you or your developer are
interested in using Magmi, let us know and we will install (and
*secure*) this program.