Create Hierarchical Taxes for State / Cities

I’ve Googled this question and see it’s a common goal of a lot of people. Though I’m having trouble following the few instructions I’ve been able to find.

I’m using a custom post type of job listings for a WP powered job board. Each of these jobs have a state and city location.

I’d like to have a page where users could browse jobs by location. This page would have a listing of all 50 “States” which are hyperlinked to search results for those states.

Underneath each “State” link I would like links to search results for each “City” that has active job listings.

I understand you can specify a tax as hierarchical when you register it, but there is no way to say to which other taxes it is a child or parent.

Further,