Automatic permalink generation for custom post types on multisite blogs?

How would I automatically generate the correct permalinks for custom post types on multisite blogs?

I have a theme on my network that uses custom post types. For those addresses to work with nice-looking URLs, it seems that the permalinks currently need to be regenerated within each blog on my network using that custom post type. Surely there’s a way to add a hook to my theme so that this is done automatically then the theme is set – has anyone done this before? Any hints?

Thanks!