custom post type permalink based off taxonomy or categories

I’ve been playing around custom post type for a bit and I just can’t get the permalinks the way I want need them.

I want to have the post permalink to be something like:
structure: %category%/%postname%

This works fine for posts using category but custom post types and pages do not have categories…

My attempt:
Custom Post Type -> Gallery (slug= gallery)
taxonomy = Florida (slug= florida)

Desired Post Permalink : http://www.example.com/gallery/florida/%postname%
Actual Permalink: http://www.example.com/gallery/%postname%

I can get this using Post categories (gallery as parent, florida as child)
Outcome -> http://www.example.com/gallery/florida/postname
but how can I do this for pages or custom post types?