How can I get Google Play store to work on my Samsung S3 mini with CyanogenMod OS?
From what you described, to me it seems like you've installed wrong Gapps package (probably for different Android version), check your gapps package, and if it's the wrong one, simply download the correct package and retry with flashing.

In case your Gapps package is correct, you might have flashed it incorrectly. In that case, you might want to reflash both the CM and Gapps files, but wipe the /system partition before flashing. Also, if you've used older Android version before switching to CyanogenMod, you should have wiped the /data partition (that might have also been the problem from what you've described).