How to hook custom taxonomies to custom post types and make the permalinks work?

Two things – I think the category URL would be: yourdomain.com/news_category/NEWS-CATEGORY-SLUG-HERE

So for example if you created a category “top headlines” in your “news_category” taxonomy… it would look like this (assuming the slug for “top headlines” is “top-headlines”):

/news_category/top-headlines/

The second thing…
I think your template name should be “taxonomy-news_category.php”

(edited to add – I don’t think you can have the slug be “category” as that is being used by WordPress already.. so that may be causing a conflict in itself…I could be wrong on that though…)