Você deve usar o PackageKit para fazer isso. A partir desse site, aqui está uma versão ligeiramente modificada do código de exemplo do python:
import dbus
try:
bus = dbus.SessionBus()
except dbus.DBusException, e:
print 'Unable to connect to dbus: %s' % str(e)
sys.exit()
try:
proxy = bus.get_object('org.freedesktop.PackageKit', '/org/freedesktop/PackageKit')
iface = dbus.Interface(proxy, 'org.freedesktop.PackageKit.Modify')
iface.InstallPackageNames(dbus.UInt32(0), ["xdotool","otherpackage","whatever"], "show-confirm-search,hide-finished")
except dbus.DBusException, e:
print 'Unable to use PackageKit: %s' % str(e)
Bônus! Isso deve funcionar no GNOME em ambos Fedora e Ubuntu.