Now that I actually know what I'm doing I understand better how powertop works.
Here's what you should look out for if you're having trouble with Powertop:
- Keep Powertop running while your laptop is on battery, Powertop needs to collect information about your battery and laptop. Neither auto-tune or calibrate will run unless Powertop has recorded enough information
- When running auto-tune, Powertop still gives me some errors as if it had failed. It actually worked just as intended.
- There is no way to make auto-tune settings permanent, but what you can do is add them to
/etc/rc.local, a script that will be launched on boot.
Here's mine for reference:
#!/bin/sh -e
#
# rc.local
#
# This script is executed at the end of each multiuser runlevel.
# Make sure that the script will "exit 0" on success or any other
# value on error.
#
# In order to enable or disable this script just change the execution
# bits.
#
# By default this script does nothing.
sudo powertop --auto-tune
exit 0
You may need to check "Allow executing file as a program" from the file's properties.

To be sure if it launched, reboot and open powertop. Switch to the "Tunables" tab, if all the options there are set as "Good", then it worked.
EDIT: By the way this actually improved my battery life by about 100%. Better than I ever got with TLP, which I am no longer using as it throttled my laptop without actually improving battery that much.