TL;DR: Try installing the policykit-1 and policykit-1-gnome packages.
You probably need polkit (a.k.a. PolicyKit).
Most graphical system administration utilities in Ubuntu, including the Software Center, can usually be run without sudo or anything quite like it. You just run them the same way you'd run any program.
When it comes time to perform a task requiring root privileges, they use polkit to perform the required actions. polkit is a separate mechanism from sudo, for allowing administrators to perform actions as root. It's installed on desktop Ubuntu systems but by default is not part of Ubuntu Server installations.
Thus the normal behavior of the Software Center is that you can invoke it simply as software-center, it will not prompt you to authenticate at that time, but then when you tell it to install or remove software, it will prompt you (graphically) to authenticate.
It sounds from your description like your system started as an Ubuntu Server system with no GUI, and then you installed a GUI. Probably the policykit-1 
and policykit-1-gnome packages have not been installed. If you install the, polkit will most likely start working for Software Center and other such utilities.
sudo apt-get update
sudo apt-get install policykit-1 policykit-1-gnome
Then you should be able to just run:
software-center
(Or select the Software Center graphically as provided for by whatever desktop environment you installed.)
If you want a fully functional Ubuntu desktop system, I recommend installing the metapackage for whatever "flavor" of Ubuntu you want to turn your system into. Basically, if you want a regular Ubuntu desktop system, install ubuntu-desktop .
sudo apt-get update
sudo apt-get install ubuntu-desktop
This should fill in the various gaps, like not having polkit, that come with installing a more minimal GUI on your server system. On the other hand, if you prefer a more minimal GUI, you can just install those polkit packages.
For more information, see How do you run Ubuntu Server with a GUI?
sudo with graphical authentication.
If you really do need run commands as root but get a graphical authentication dialog, what you're looking for is gksudo (or gksu). This is provided by the gksu package. It is a graphical frontend for sudo.
Typically gksudo is used to run graphical applications as root (or some other user besides the user launching them). But you can also use it to run non-graphical commands--provided the commands can be run with sudo.
You can run gksudo from a terminal but you don't have to. You can run it from the Alt+F2 (run command) dialog or put it in the Exec= line of a .desktop file (or any of the other ways you run graphical programs).
Note that you should consider using gksudo to run graphical applications as root even when you are running them from a terminal, because commands like sudo ... where ... is a graphical application can actually break the per-application configurations of the non-root users running them. (Fortunately this is fixable.) sudo gedit is particularly notorious.
For more information on the problem with sudo for graphical applications and what to do instead, see:
There's also polkit-based graphical way ...for non-graphical commands.
gksudo works fine for running both graphical and non-graphical programs. You should probably use that.
But an alternative, using polkit instead of sudo and only working for non-graphical programs, is pkexec.
For example, if you run pkexec touch /root/foo.txt, you'll be prompted with a graphical authentication dialog, and if the authentication succeeds, touch /root/foo.txt is run, creating (or freshening) foo.txt in the /root folder.
pkexec will use a non-graphical dialog, requiring a terminal, in the event that it cannot create a graphical dialog. But this is unlikely to happen if you're running it through a facility provided by your graphical shell or desktop environment.- Why does
pkexec work only for non-graphical programs? Actually it also runs graphical programs, but only if polkit has been specially configured to allow it--which is not usually done. See man pkexec (and the upstream version, with screenshots), this answer and that answer for some details, if you're interested.
sudo vs. polkit (some technical details, only if you're interested)
A new gksu/gksudo will use polkit instead of sudo to do its work, though this version has not been widely adopted. I mainly bring it up to recommend the README file in its source code (written by Gustavo Noronha Silva), which explains the important differences between sudo and polkit. To quote from it briefly:
PolicyKit solves the problem of an application needing higher
privileges by providing facilities to let users authenticate
themselves and for applications to verify authentication and
authorization information. The application has to be structured in a
way that all privileged operation is done by a (preferably) small
D-Bus service, which is commanded by the unprivileged code. All
"actions" that are performed need proper authorization, which is
handled through Policykit.
4. Why maintain gksu?
So, this essentially makes gksu unnecessary, since applications no
longer need to run as a privileged user, and user authentication is
done by PolicyKit's Auth Agent. But applications need to be refactored
to adopt this new structure, and there are some cases in which what
you want is indeed something that runs programs as root.
These issues underlie the situation I believe you're in:
- Software Center is designed to use polkit for privilege elevation, so that only specific actions need to be performed as root. For this, it needs polkit, which was missing (or broken) on your system.
- Because it is designed to use polkit, there's no pre-made launcher to start the Software Center as root. polkit obviates the need to run graphical administration tools as root, most of the time.
- But sometimes you really do need to run a graphical program as root. In that case, you can use
gksu/gksudo.
(...Which may eventually use polkit behind the scenes--but the gksudo currently in Ubuntu is the traditional one that uses sudo).
