You allocate spending to train spies from your Domestic Stats.  Espionage spending is at the bottom, below your production sliders.

There's also a separate tab for espionage, where you can place agents on civilizations (in 2.0), and it shows you the time until your next spy is trained.

You don't need any tech researched to start training spies.

Building a Counter Espionage Center on a planet makes that planet (and that planet alone) immune to spies.

I noticed that if I build a "Counter Espionage Center" on a planet where spies are already present it will not negate them.  It prevents further spies from being placed.  (Shouldn't they look for spies to negate once they are built ? ). 

I rushed researched 2 tech and bought that project hoping to negate 3 spies on one of my world but it didn't work. 

I had to wait to get spies and negate those one by one.