My Subscribe to mailing list only works with logged in users
There are some permissions with profiles and you have to set those permissions for the anonnymous user. Those permissions are calles profile listsing. 

If you are using Drupal you could try to create a webform with the webform and civicrm integration.