How can I set the Software Center to install software for non-root users?

You can modify the PolicyKit permissions to allow the users to access the aptdaemon backend that Software Centre uses.

dpkg --listfiles aptdaemon shows that /usr/share/polkit-1/actions/org.debian.apt.policy is the file specifying the actions possible on the aptdaemon backend.

Looking in that file, the < action id=""> tags specify the possible actions. You'd probably want org.debian.apt.install-packages to allow users to install new packages from the archive, and org.debian.apt.update-cache to allow users to update the package lists.

See man pklocalauthority which documents how to set local permissions on PolicyKit actions. Putting the following into /etc/polkit-1/localauthority/50-local.d/10-allow-users-to-install.pkla will allow any user logged in to the local machine to install packages after typing their own password (even when they're not in the admin group) and to update the package cache without typing any password.

[Untrusted Install]
Action=org.debian.apt.install-or-remove-packages
ResultyAny=no
ResultInactive=no
ResultActive=auth_self

[Untrusted Update]
Action=org.debian.apt.update-cache
ResultAny=no
ResultInactive=no
ResultActive=yes

I don't think it's currently possible to do so via the GUI, but the following should work, albeit be a little kludgy. YMMV.

Add the following line to /etc/sudoers (use sudo visudo to edit the file):

%packageinstallers ALL = NOPASSWD: /usr/bin/software-center /usr/bin/apt-get

Then you just need to create and add the specific users to the packageinstallers group:

$ sudo addgroup packageinstallers
$ sudo adduser jdoe packageinstallers

Now jdoe can do the following:

$ sudo apt-get install <some-package>

and you can edit the desktop menu item for the Software Center so that it call on software-center prepending the command with gksudo.

PolicyKit may allow you to do so without sudo, but it's beyond my understanding at this point.

RAOF's answer applies to Ubuntu only. Kubuntu uses QAptWorker as backend (observed for Natty and Oneiric). To allow for non-root installations, create /etc/polkit-1/localauthority/50-local.d/10-allow-non-root-install-packages.pkla containing:

[Update Software Sources]
Action=org.kubuntu.qaptworker.updateCache
ResultAny=no
ResultInactive=no
ResultActive=yes

[Install Software]
Action=org.kubuntu.qaptworker.commitChanges
ResultAny=no
ResultInactive=no
ResultActive=auth_self

I wanted to allow some non-admin users to install software while not granting sudo access directly. That was accomplished by inserting the next lines in both configuration groups:

Identity=unix-user:some-non-admin-user

If there is a group that must be granted permission, use unix-group instead of unix-user.