What is the permission needed to add permissions? I'm creating an automated backup, upload, restore and user creation utility for a process here at my company. I've got everything up until the user creation all set. I've got a freshly restored database that I need to create a user in so that the application can connect to it.

So my problem is two-fold - I've got a user with sufficient permissions over master to restore the database, but I can't seem to figure out what permissions that user needs to be able to USE the newly restored database.

Once I've got that, I think I can use sp_change_users_login to reconcile the user with the database, but I can't seem to crack that. 

BTW, if it wasn't clear, this needs to be done through T-SQL, unless it's a one-time permission that can be added through SSMS.
To change permissions within the restored database the account which the automation is using will need to be a member of the securityadmin fixed server role.  That'll give you rights to create a user within the database and give that user permissions within the database.

Using sp_change_users_login requires that the login which is running it be a member of the db_owners fixed database role within the database you are running it.