Views: Can I create views based on taxonomies that link to other, context-specific taxonomy-based views?
One solution is to create a view showing taxonomy terms. 

Display 1

Create a page display with a path "documents"

Add a relationship "Taxonomy term: Content using &lt;state vocab&gt;." Require this relationship.

Under Other > Query Settings select Distinct

Add fields 


Taxonomy term: Term ID 
Taxonomy term: Name


Exclude term ID from display

Rewrite the results of Name > Rewrite the output of this field: 
&lt;a href="/documents/[tid]"&gt;[name]&lt;/a&gt;

Add a filter Content: Type (= &lt;your document content type&gt;)

Display 2

Create a new page display with a path "documents/%"

Remove the Relationship for the state for "This page (override)" and add a relationship for your Department taxonomy. Require this relationship.

Add a contextual filter for Content: &lt;state field&gt; and display contents of "No results found" when filter value is not in the URL.

Edit the rewrite value of your name field, make sure to select "This page (override)": &lt;a href="/documents/!1/[tid]"&gt;[name]&lt;/a&gt;

Display 3

Create a third page display with a path "documents/%/%"

Keep the state relationship from the view's defaults, but add a relationship using "This page (override)" for your Department taxonomy. Require this relationship.

Add a contextual filter, override for this display, for Content: State and then add one for Content: Department.

Override your fields for this display, removing the Term ID and Term Name, and add a field for Content: Title.

If I have explained this well enough, display 1 should give you a list of states that link to display 2 using the contextual filter to give a list of departments from that state, linking to display 3 showing a list of your document node titles from that state department.