Add a contact to an organization through "profile" public form
I think that in pure CiviCRM all you can do is add the Current Employer field to the profile, which is then a text only field.

If you want that field to be an autocomplete then I think you should try the Public Autocomplete of Organisation Names extension. There is also a blog written about it here