Hierarchical taxonomy breadcrumb
These are two separate questions. One about the path, another about the breadcrumb.

Breadcrumbs:

Disclaimer: The solution presented here may need more tweaking, if your taxonomy/term/% is replaced by a views page with contextual filter. (I never do that, there are other ways to achieve the same)

Crumbs will do the trick. 90% of the task out of the box. If not, check this doc: http://drupal.org/node/1984484  

You need some manual work to make "/category" the top-level breadcrumb item for all the terms: (this explanation is for the 7.x-2.x branch)
Visit Admin > Structure > Crumbs > Entity parent > Taxonomy
Set 'category' as the parent path for your vocabulary.
Go back to Admin > Structure > Crumbs
Move crumbs.entityParent.* into the "Enabled" section, and give it a low enough priority.

Path:

I suppose you have pathauto installed already.
Go to Admin > Configuration > Search and metadata > URL aliases
Look at "Taxonomy term paths".

I read somewhere that the following pattern will do the trick:

category/[term:parents:join-path]/[term:name]


Not tested myself. Good luck with it :)