How to add terms by users in node edit/create form?

I don't think Hierarchical Select can let users add terms. You could use http://drupal.org/project/select_or_other or http://drupal.org/project/cck_select_other to let users choose from existing terms or add a term. But then you don't have the hirarchical select widget. Mabe you want to create an issue on the Hierarchical Select module (if it's not there yet).