I used a backup app to first make a backup of the .apk file of the system app, and then uninstalled it. When I try installing it again, I get "application not installed".
How can I go about that? I don't know in which place the .apk was stored originally.
Usually, you put the APK back to where you deleted it from. As in your case you didn't check that (but used a backup app to extract it), that "original place" usually is /system/priv-app. Check the structure in that directory (it differs between Android versions), then place your .apk accordingly. After that, don't forget to reboot – as only after that the APK will be loaded.
Note (you know that but others might miss it): in order to write to /system you need to mount it read-write first:
su
mount -o remount,rw /system
# do the copy here
mount -o remount,ro /system
As you have to reboot anyway, you can skip the last step as the boot process then takes care for it.
Q & A