And, I didn't even want Gapps! I only wanted Play Store, like many of you reading this. So, this was what I did.
1) Download the zip file below. All of the apk files were taken from the latest PA-Gapps package for 4.4.4 .
2)Extract the files to your device, put them on some folder.
3)Use a root explorer (like CM File Manager, which comes with CyanogenMod), and copy the 4 apk files to /system/priv-app
4)Now set the permissions. (You can do it via the terminal, set the permissions to 644, but this is easier). All files must be set like this.
5)Finally, reboot. Open Play Store. Ta-da
DISCLAIMER: I shall not be held responsible for any damage dealt to any device.