There are plenty of security apps that can require a password to
uninstall apps, but I'm finding it harder to find one that enforces a password when installing!
So, I reckon it depends on how they installed it in the first place. If they have your google account password they could install over the air using the Play Store on the web, so you should change your password.
Otherwise, assuming they had physical access to the phone, and you can't be sure that won't happen again, here a few things you could do:
1) require a password or pattern to unlock the phone, or change it if you already had that. There is a time-out in your security settings, so set it to come on quickly after the screen turns off (if it only kicks in a few minutes after the screen goes off that might give someone access). Get into the habit of wiping the screen so that the pattern isn't visible from marks your fingers leave.
2) turn off the option to install apps from unknown sources, and also turn off usb debugging if enabled (check developer options menu). That last will stop someone with a computer and a cable installing apps over usb without unlocking the phone.
3) there are apps which can be used to password-protect other apps.
This one is the top hit I got from Google, but you can see from that page that there are many similar apps. I've never used one of these, but I figure that if you use one to password protect both the Play Store app and the Settings app that would make it a lot harder for someone to install stuff if they got their hands on your phone (password protecting Settings should stop them undoing some of the other stuff, or removing the password app).
That's all I can think of at the moment. If your phone it rooted you could use a firewall app (such as droidwall) or a security app such as Avast to firewall the phone - set it to whitelist mode (so only apps you select are allowed to access the net) and, assuming the spyware is using the internet to report things, you would block the app from reporting to its installer.
