Making Time Machine Remember Credentials

  1. Connect to the share with credentials (connect as)
  2. Hold down option, command and drag the share to the desktop
  3. Open System Preferences, go to Users & Groups
  4. Click on Login Items
  5. Click the plus icon and add the folder that was just added to the desktop

Now choose the share in Time Machine!