Icons for Facetime and the App Store keep re-appearing in my dock after a restart. How can I get rid of them?
Do other apps remain in the dock after being removed and restarted?
Does this behavior also occur when you log out and back in?

I'll assume yes on both until more information is supplied:

Barring some extraneous application modifying the dock .plist (which is unlikely that you're unaware of) it might be locked or otherwise unwritable for you.  Check the permissions on your ~/Library/Preferences/com.apple.dock.plist file, making sure you have Read/Write.

If you want, you can modify the file directly to see if you have the rights to do so, but theres a whole lot that can go wrong with that.  Instead, modify your dock and see if the file's date modified changes.  If it doesn't, your dock isn't writing the plist correctly.

If it's not a big issue, you can simply back-up and delete the com.apple.plist file and reconfigure the dock to your liking.