You could use my plugin:
http://wordpress.org/extend/plugins/custom-post-permalinks/
That will only work if it’s a non-hierarchical post type.
If it’s hierarchical, you’re going to have to register the permastruct yourself. This is a huge ordeal which I don’t have the time to write out at the moment. You can look at the code in my plugin above and try to work it out for yourself. Some pointers:
- In order to get the category into the URL, you’re going to have to hook into the
'post_type_link' - You’ll also have to hook into
'parse_request'to make sure the post type is recognized.